Some results on total domination in direct products of graphs

Paul Dorbec; Sylvain Gravier; Sandi Klavžar; Simon Spacapan

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 103-112
  • ISSN: 2083-5892

Abstract

top
Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.

How to cite

top

Paul Dorbec, et al. "Some results on total domination in direct products of graphs." Discussiones Mathematicae Graph Theory 26.1 (2006): 103-112. <http://eudml.org/doc/270561>.

@article{PaulDorbec2006,
abstract = {Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the \{2\}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.},
author = {Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Spacapan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {direct product; total domination; k-tuple domination; open packing; domination; bound; domination number},
language = {eng},
number = {1},
pages = {103-112},
title = {Some results on total domination in direct products of graphs},
url = {http://eudml.org/doc/270561},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Paul Dorbec
AU - Sylvain Gravier
AU - Sandi Klavžar
AU - Simon Spacapan
TI - Some results on total domination in direct products of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 103
EP - 112
AB - Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
LA - eng
KW - direct product; total domination; k-tuple domination; open packing; domination; bound; domination number
UR - http://eudml.org/doc/270561
ER -

References

top
  1. [1] B. Bresar, S. Klavžar and D.F. Rall, Dominating direct products of graphs, submitted, 2004. Zbl1116.05055
  2. [2] M. El-Zahar, S. Gravier and A. Klobucar, On the total domination of cross products of graphs, Les Cahiers du laboratoire Leibniz, No. 97, January 2004. Zbl1168.05344
  3. [3] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. Zbl0993.05104
  4. [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998). 
  5. [5] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7. Zbl0955.68089
  6. [6] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (J. Wiley & Sons, New York, 2000). Zbl0963.05002
  7. [7] P.K. Jha, S. Klavžar and B. Zmazek, Isomorphic components of Kronecker product of bipartite graphs, Discuss. Math. Graph Theory 17 (1997) 301-309, doi: 10.7151/dmgt.1057. Zbl0906.05050
  8. [8] R. Klasing and C. Laforest, Hardness results and approximation algorithms of k-tuple domination in graphs, Inform. Process. Lett. 89 (2004) 75-83, doi: 10.1016/j.ipl.2003.10.004. Zbl1178.68682
  9. [9] C.S. Liao and G.J. Chang, Algorithmic aspect of k-tuple domination in graphs, Taiwanese J. Math. 6 (2002) 415-420. Zbl1047.05032
  10. [10] R. Nowakowski and D. F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79, doi: 10.7151/dmgt.1023. Zbl0865.05071
  11. [11] D.F. Rall, Total domination in categorical products of graphs, Discuss. Math. Graph Theory 25 (2005) 35-44, doi: 10.7151/dmgt.1257. Zbl1074.05068
  12. [12] P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962) 47-52, doi: 10.1090/S0002-9939-1962-0133816-6. Zbl0102.38801

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.