Download PDF - Associative graph products and their independence, domination and coloring numbersAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Associative graph products and their independence, domination and coloring numbers

Authors 1, 2

Affiliations

  1. Dalhousie University
  2. Furman University

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

ENG
graph products, independence, domination, irredundance, coloring

Bibliography

  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čisl. Sistemy 9 (1963) 30-43; MR 35 #81.
Discussiones Mathematicae Graph Theory
1996/16/1
Export to PBN, Opens in new tab
Pages:
53-79
Main language of publication
English
Received
1996-01-15
Accepted
1996-05-01
Published
1996
Exact and natural sciences