ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 16(1) (1996) 53-79
Richard J. Nowakowski
Dalhousie University, Halifax, Nova Scotia, Canada
Douglas F. Rall
Furman University, Greenville, SC 29613 U.S.A.
Associative products are defined using a scheme of Imrich & Izbicki . These
include the Cartesian, categorical, strong and lexicographic products, as well as others.
We examine which product ⊗ and parameter p pairs are
multiplicative, that is, p(G⊗H) ≥
p(G)p(H) for all graphs G and H or p(G⊗H) ≤
p(G)p(H) for all graphs G and H. The parameters are related to independence, domination
and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon
capacity of a graph and Hedetniemi's coloring conjecture.
Keywords: graph products, independence, domination, irredundance, coloring.
1991 Mathematics Subject Classification: 05C99.