On trees with double domination number equal to the 2-outer-independent domination number plus one

Abstract

A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G, such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G = (V,E), a subset D ⊆ V (G) is a 2-dominating set if every vertex of V (G) \ D has at least two neighbors in D, while it is a 2-outer-independent dominating set of G if additionally the set V (G)\D is independent. The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G. This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.

Keywords

Double domination / 2-Outer-independent domination / 2-Domination Tree

References

[1] Atapour M., Khodkar A., Sheikholeslami S.. Characterization of double domination subdivision number of trees. Discrete Appl. Math., 2007, 155: 1700-1707

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

[3] Blidia M., Favaron O., Lounes R.. Locating-domination, 2-domination and independence in trees. Australas. J. Combin., 2008, 42: 309-316

[4] Chen X., Sun L.. Some new results on double domination in graphs. J. Math. Res. Exposition, 2005, 25: 451-456

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

[6] Fujisawa J., Hansberg A., Kubo T. Independence and 2-domination in bipartite graphs. Australas. J. Combin., 2008, 40: 265-268

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

[8] Harant J., Henning M.. A realization algorithm for double domination in graphs. Util. Math., 2008, 76: 11-24

[9] Harary F., Haynes T.. Double domination in graphs. Ars Combin., 2000, 55: 201-213

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

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

[12] Jiao Y., Yu H.. On graphs with equal 2-domination and connected 2-domination numbers. Math. Appl. (Wuhan), 2004, 17(suppl.): 88-92

[13] Krzywkowski, M., 2-Outer-independent domination in graphs, submitted.

[14] Shaheen R.. Bounds for the 2-domination number of toroidal grid graphs. Int. J. Comput. Math., 2009, 86: 584-588