On the ratio between 2-domination and total outer-independent domination numbers of trees

Abstract

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V (G) | D has at least two neighbors in D. A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V (G) | D is independent. The 2-domination (total outer-independent domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (total outer-independent dominating, respectively) set of G. We investigate the ratio between 2-domination and total outer-independent domination numbers of trees.

Keywords

2-Domination / Total domination / Total outer-independent domination / Tree

References

[1] Allan R, Laskar R, Hedetniemi S. A note on total domination. Discrete Mathematics, 1984, 49: 7-13

[2] Arumugam S, Thuraiswamy A. Total domination in graphs. Ars Combinatoria, 1996, 43: 89-92

[3] Atapourm M, Soltankhah N. On total dominating sets in graphs. International Journal of Contemporary Mathematical Sciences, 2009, 4: 253-257

[4] Blidia M, Chellali M, Volkmann L. Bounds of the 2-domination number of graphs. Utilitas Mathematica, 2006, 71: 209-216

[5] Blidia M, Favaron O, Lounes R. Locating-domination, 2-domination and independence in trees. Australasian Journal of Combinatorics, 2008, 42: 309-316

[6] Chellali M, Favaron O, Haynes T, Raber D. Ratios of some domination parameters in trees. Discrete Mathematics, 2008, 308: 3879-3887

[7] Cockayne E, Dawes R, Hedetniemi S. Total domination in graphs. Networks, 1980, 10: 211-219

[8] Dankelmann P, Day D, Hattingh J On equality in an upper bound for the restrained and total domination numbers of a graph. Discrete Mathematics, 2007, 307: 2845-2852

[9] Dorfling M, Goddard W, Henning M. Domination in planar graphs with small diameter II. Ars Combinatoria, 2006, 78: 237-255

[10] El-Zahar M, Gravier S, Klobucar A. On the total domination number of cross products of graphs. Discrete Mathematics, 2008, 308: 2025-2029

[11] Favaron O, Karami H, Sheikholeslami S. Total domination in K ₅- and K ₆-covered graphs. Discrete Mathematics and Theoretical Computer Science, 2008, 10: 35-42

[12] Fink J, Jacobson M. n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science, 1985, New York: Wiley 282-300

[13] Frendrup A, Vestergaard P, Yeo A. Total domination in partitioned graphs. Graphs and Combinatorics, 2009 181-196

[14] Fujisawa J, Hansberg A, Kubo T Independence and 2-domination in bipartite graphs. Australasian Journal of Combinatorics, 2008, 40: 265-268

[15] Hansberg A, Volkmann L. On graphs with equal domination and 2-domination numbers. Discrete Mathematics, 2008, 308: 2277-2281

[16] Haynes T, Hedetniemi S, Slater P. Fundamentals of Domination in Graphs, 1998, New York: Marcel Dekker

[17] Haynes T, Hedetniemi S, Slater P. Domination in Graphs: Advanced Topics, 1998, New York: Marcel Dekker

[18] Henning M, McCoy J. Total domination in planar graphs of diameter two. Discrete Mathematics, 2009, 309: 6181-6189

[19] Ho P. A note on the total domination number. Utilitas Mathematica, 2008, 77: 97-100

[20] Jiao Y, Yu H. On graphs with equal 2-domination and connected 2-domination numbers. Mathematica Applicata, 2004, 17(suppl): 88-92

[21] Krzywkowski, M., Total outer-independent domination in graphs, submitted.

[22] Shaheen R. Bounds for the 2-domination number of toroidal grid graphs. International Journal of Computer Mathematics, 2009, 86: 584-588

[23] Thomass S, Yeo A. Total domination of graphs and small transversals of hypergraphs. Combinatorica, 2007, 27: 473-487

[24] Zwierzchowski M. Total domination number of the conjunction of graphs. Discrete Mathematics, 2007, 307: 1016-1020