Some results on total domination in direct products of graphs
Paul Dorbec ; Sylvain Gravier ; Sandi Klavžar ; Simon Spacapan
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 103-112 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270561 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1305,
     author = {Paul Dorbec and Sylvain Gravier and Sandi Klav\v zar and Simon Spacapan},
     title = {Some results on total domination in direct products of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {103-112},
     zbl = {1103.05059},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1305}
}

Paul Dorbec; Sylvain Gravier; Sandi Klavžar; Simon Spacapan. Some results on total domination in direct products of graphs. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 103-112. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1305/

[000] [1] B. Bresar, S. Klavžar and D.F. Rall, Dominating direct products of graphs, submitted, 2004. | Zbl 1116.05055

[001] [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. | Zbl 1168.05344

[002] [3] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. | Zbl 0993.05104

[003] [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).

[004] [5] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7. | Zbl 0955.68089

[005] [6] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (J. Wiley & Sons, New York, 2000). | Zbl 0963.05002

[006] [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. | Zbl 0906.05050

[007] [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. | Zbl 1178.68682

[008] [9] C.S. Liao and G.J. Chang, Algorithmic aspect of k-tuple domination in graphs, Taiwanese J. Math. 6 (2002) 415-420. | Zbl 1047.05032

[009] [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. | Zbl 0865.05071

[010] [11] D.F. Rall, Total domination in categorical products of graphs, Discuss. Math. Graph Theory 25 (2005) 35-44, doi: 10.7151/dmgt.1257. | Zbl 1074.05068

[011] [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. | Zbl 0102.38801