DMGT

Discussiones Mathematicae Graph Theory 16(1) (1996) 53-79
DOI: https://doi.org/10.7151/dmgt.1023

ASSOCIATIVE GRAPH PRODUCTS AND THEIR INDEPENDENCE, DOMINATION AND COLORING NUMBERS

Richard J. Nowakowski

Dalhousie University, Halifax, Nova Scotia, Canada B3J 3J5

Douglas F. Rall

Furman University, Greenville, SC 29613 U.S.A.

Abstract

Associative products are defined using a scheme of Imrich & Izbicki [18]. 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.

References

[1]	M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt International Series, 1979).
[2]	C. Berge, The Theory of Graphs and Its Applications (London, Methuen, 1962) MR 24 #A2381.
[3]	M. Borowiecki, On chromatic number of products of two graphs, Coll. Math. 25 (1972) 49-52; MR 46 #1630.
[4]	M. Borowiecki, On the graphs with minimaximal kernels, Scientific Papers Inst. Math. Wroc aw Techn. Univ. 17 (1977) 3-7; Zbl. 398:05C064.
[5]	E.J. Cockayne, S.T. Hedetniemi and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978) 461-468; MR 80m:05087.
[6]	M. El-Zahar and N. W. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985) 121- 126; MR 87a:05067.
[7]	D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory (B) 19 (1975) 87-95; MR 52#13462.
[8]	E.N. Gilbert, Unpublished Technical Memorandum, Bell Telephone Laboratories, Murray Hill, New Jersey (1972).
[9]	F. Harary and G. W. Wilcox, Boolean operations on graphs, Math. Scand. 20 (1967) 41-51; MR 35 #2775.
[10]	B. Hartnell and D. Rall, On Vizing's Conjecture, Congressus Numerantium 82 (1991) 87-96; MR 92k:05071.
[11]	B. Hartnell and D. Rall, Vizing's conjecture and the one-half argument, Discussiones Mathematicae-Graph Theory 15 (1995) 205-216, doi: 10.7151/dmgt.1018.
[12]	S. T. Hedetniemi, Homomorphisms of graphs and automata, University of Michigan Technical Report 03105-44-T (1966).
[13]	P. Hell and D.J. Miller, Achromatic numbers and graph operations, Discrete Math. 108 (1992) 297-305; MR 93k:05062.
[14]	P. Hell and F.S. Roberts, Analogues of the Shannon capacity of a graph, Theory and practice of combinatorics, SE-North-Holland Math. Stud., 60, North-Holland, Amsterdam-New York (1982) 155-168; MR 86k:05053.
[15]	A.J.W. Hilton, R. Rado and S.H. Scott, A (< 5)-colour theorem for planar graphs, Bull. London Math. Soc. 5 (1973) 302-306; MR 48 #1960.
[16]	L.-H. Hsu, On a multiplicative graph function conjecture, Discrete Math. 45 (1983) 245-253; MR 84j:05099.
[17]	L.-H. Hsu, On a strongly multiplicative graph function conjecture, Chinese J. Math. 13(2) (1985) 103-108; MR 87a:05127.
[18]	W. Imrich and H. Izbicki, Associative Products of Graphs, Monatshefte für Mathematik 80 (1975) 277-281; MR 53 #7864.
[19]	M.S. Jacobson and L.S. Kinch, On the domination of the products of graphs II, trees, J. Graph Theory 10 (1986) 97-106; MR 87e:05056.
[20]	L. Lovász, On the Shannon Capacity of a Graph, IEEE Trans. on Inform. Theory, IT-25(1) (1979) 1-7; MR 81g:05095.
[21]	J. Ne set ril and V. Rödl, Products of graphs and their applications, in: Graph Theory, agów 1981 (Lecture Notes in Mathematics 1018, Springer, Berlin, 1983) 151-160; MR 85d:05179.
[22]	R.J. Nowakowski and D. Rall, A survey of the introduction and history of graph products, preprint.
[23]	O. Ore, Theory of Graphs (Amer. Math. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, R.I., 1962).
[24]	V. Pus, Chromatic number of products of graphs, Comment. Math. Univ. Carolin. 29 (1988) 457-463; MR 90a:05088.
[25]	F.S. Roberts, Graph theory and its applications to problems of society, CBMS-NSF monographs (1978) #29 (S.I.A.M, Philadelphia, PA); MR 80g:90036.
[26]	F.S. Roberts, On the mobile radio frequency assignment problem and the traffic light phasing problem, in: Second International Conference on Combinatorial Mathematics (New York, 1978), Annals New York Acad. Sci. 319 (1979) 466-483; MR 81e:05071.
[27]	M. Rosenfeld, On a Problem of C.E. Shannon in Graph Theory, Proc. Amer. Math. Soc. 18 (1967) 315-319; MR 34 #7405.
[28]	G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957) 515-525; MR 20 #1322.
[29]	G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-696; MR 22 #1524.
[30]	C.E. Shannon, The zero error capacity of a noisy channel, I.R.E., Trans. on Inform. Theory, IT-2 (1956) 8-19; MR 19 #623.
[31]	V.G. Vizing, The cartesian product of graphs, Vy cisl. Sistemy 9 (1963) 30-43; MR 35 #81.