A subset D ⊆ V (G) in a graph G is a dominating set if every vertex in V (G) \ D is adjacent to at least one vertex of S. A subset S ⊆ V (G) in a graph G is a 2-independent set if ∆(G[S])<2. The 2-independence number α2(G) is the order of a largest 2-independent set in G. Further, a subset D ⊆ V (G) in a graph G is a 2-independent dominating set if D is both dominating and 2-independent. The 2-independent domination number i2(G) is the order of a smallest 2-independent dominating set in G. In this paper, we characterize all trees T of order n with i2(T) = n/2. Moreover, we prove that for any tree T of order n≥2, i2(T)≤2/3α2(T), and this bound is sharp.
Gang Zhang, Baoyindureng Wu
. 2-Independent Domination in Trees[J]. Journal of the Operations Research Society of China, 2024
, 12(2)
: 485
-494
.
DOI: 10.1007/s40305-022-00428-2
[1] Bondy, J.A., Murty, U.S.R.:Graph Theory. Springer, New York (2008)
[2] Fink, J.F., Jacobson, M.S.:n-domination in graphs. In:Graph Theory with Applications to Algorithms and Computer Science, pp. 283-300. Wiley, New York (1985)
[3] Fink, J.F., Jacobson, M.S.:On n-domination, n-dependence and forbidden subgraphs. In:Graph Theory with Applications to Algorithms and Computer Science, pp. 301-311. Wiley, New York (1985)
[4] Favaron, O.:k-domination and k-independence in graphs. Ars Combin. 25, 159-167(1988)
[5] Blidia, M., Chellali, M., Favaron, O., Meddah, N.:Maximal k-independent sets in graphs. Discuss. Math. Graph Theory 28, 151-163(2008)
[6] Chellali, M., Favaron, O., Hansberg, A., Volkmann, L.:k-domination and k-independence in graphs:A survey. Graphs Combin. 28, 1-55(2012)
[7] Favaron, O.:On a conjecture of Fink and Jacobson concerning k-domination and k-independence. J. Combin. Theory Ser. B 39, 101-102(1985)
[8] Favaron, O., Hedetniemi, S.M., Hedetniemi, S.T., Rall, D.F.:On k-dependent domination. Discrete Math. 249, 83-94(2002)
[9] Hansberg, A., Pepper, R.:On k-domination and j-independence in graphs. Discrete Appl. Math. 161, 1472-1480(2013)
[10] Desormeaux, W.J., Henning, M.A.:Paired domination in graphs:a survey and recent results. Util. Math. 94, 101-166(2014)
[11] Goddard, W., Henning, M.A.:Independent domination in graphs:a survey and recent results. Discrete Math. 313, 839-854(2013)
[12] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.:Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York (1998)
[13] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.(eds.):Domination in Graphs:Advanced Topics. Marcel Dekker Inc., New York (1998)
[14] Henning, M.A.:A survey of selected recent results on total domination in graphs. Discrete Math. 309, 32-63(2009)
[15] Chellali, M., Favaron, O., Haynes, T., Raber, D.:Ratios of some domination parameters in trees. Discrete Math. 308, 3879-3887(2008)
[16] Favaron, O.:A bound on the independent domination number of a tree. J. Graph Theory 1, 19-27(1992)
[17] Haynes, T.W., Henning, M.A.:A characterization of i-excellent trees. Discrete Math. 248, 69-77(2002)
[18] Lemá nska, M.:Lower bound on the domination number of tree. Discuss. Math. Graph Theory 24, 165-169(2004)
[19] Ma, D., Chen, X.:A note on connected bipartite graphs having independent domination number half their order. Appl. Math. Lett. 17, 959-962(2004)
[20] Dehgardi, N., Sheikholeslami, S.M., Valinavaz, M., Aram, H., Volkmann, L.:Domination numbers, independent domination number and 2-independence number in trees. Discuss. Math. Graph Theory 41, 39-49(2021)
