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

Abstract

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

How to cite

top

Richard 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. [1] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt International Series, 1979). Zbl0403.05027
  2. [2] C. Berge, The Theory of Graphs and Its Applications (London, Methuen, 1962) MR 24 #A2381. 
  3. [3] M. Borowiecki, On chromatic number of products of two graphs, Coll. Math. 25 (1972) 49-52; MR 46 #1630. Zbl0239.05114
  4. [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. [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. [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. [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. [8] E.N. Gilbert, Unpublished Technical Memorandum, Bell Telephone Laboratories, Murray Hill, New Jersey (1972). 
  9. [9] F. Harary and G. W. Wilcox, Boolean operations on graphs, Math. Scand. 20 (1967) 41-51; MR 35 #2775. Zbl0152.22801
  10. [10] B. Hartnell and D. Rall, On Vizing's Conjecture, Congressus Numerantium 82 (1991) 87-96; MR 92k:05071. 
  11. [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. [12] S. T. Hedetniemi, Homomorphisms of graphs and automata, University of Michigan Technical Report 03105-44-T (1966). 
  13. [13] P. Hell and D.J. Miller, Achromatic numbers and graph operations, Discrete Math. 108 (1992) 297-305; MR 93k:05062. Zbl0760.05040
  14. [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. [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. [16] L.-H. Hsu, On a multiplicative graph function conjecture, Discrete Math. 45 (1983) 245-253; MR 84j:05099. 
  17. [17] L.-H. Hsu, On a strongly multiplicative graph function conjecture, Chinese J. Math. 13(2) (1985) 103-108; MR 87a:05127. 
  18. [18] W. Imrich and H. Izbicki, Associative Products of Graphs, Monatshefte für Mathematik 80 (1975) 277-281; MR 53 #7864. Zbl0328.05136
  19. [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. [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. [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. [22] R.J. Nowakowski and D. Rall, A survey of the introduction and history of graph products, preprint. 
  23. [23] O. Ore, Theory of Graphs (Amer. Math. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, R.I., 1962). 
  24. [24] V. Pus, Chromatic number of products of graphs, Comment. Math. Univ. Carolin. 29 (1988) 457-463; MR 90a:05088. 
  25. [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. [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. [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. [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. [29] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-696; MR 22 #1524. Zbl0095.37802
  30. [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. [31] V.G. Vizing, The cartesian product of graphs, Vyčisl. Sistemy 9 (1963) 30-43; MR 35 #81. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.