# Associative graph products and their independence, domination and coloring numbers

Richard J. Nowakowski; Douglas F. Rall

Discussiones Mathematicae Graph Theory (1996)

- Volume: 16, Issue: 1, page 53-79
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRichard J. Nowakowski, and Douglas F. Rall. "Associative graph products and their independence, domination and coloring numbers." Discussiones Mathematicae Graph Theory 16.1 (1996): 53-79. <http://eudml.org/doc/270228>.

@article{RichardJ1996,

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.},

author = {Richard J. Nowakowski, Douglas F. Rall},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph products; independence; domination; irredundance; coloring; products},

language = {eng},

number = {1},

pages = {53-79},

title = {Associative graph products and their independence, domination and coloring numbers},

url = {http://eudml.org/doc/270228},

volume = {16},

year = {1996},

}

TY - JOUR

AU - Richard J. Nowakowski

AU - Douglas F. Rall

TI - Associative graph products and their independence, domination and coloring numbers

JO - Discussiones Mathematicae Graph Theory

PY - 1996

VL - 16

IS - 1

SP - 53

EP - 79

AB - 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.

LA - eng

KW - graph products; independence; domination; irredundance; coloring; products

UR - http://eudml.org/doc/270228

ER -

## References

top- [1] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt International Series, 1979). Zbl0403.05027
- [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. Zbl0239.05114
- [4] M. Borowiecki, On the graphs with minimaximal kernels, Scientific Papers Inst. Math. Wroc aw Techn. Univ. 17 (1977) 3-7; Zbl. 398:05C064. Zbl0398.05064
- [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. Zbl0393.05044
- [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. Zbl0282.05114
- [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. Zbl0152.22801
- [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. Zbl0845.05074
- [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. Zbl0760.05040
- [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. Zbl0278.05103
- [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. Zbl0328.05136
- [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. Zbl0584.05053
- [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. Zbl0452.05001
- [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. Zbl0147.42801
- [28] G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957) 515-525; MR 20 #1322. Zbl0079.39202
- [29] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-696; MR 22 #1524. Zbl0095.37802
- [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čisl. Sistemy 9 (1963) 30-43; MR 35 #81.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.