Geodesic
On Independent [1, 2]-Sets in Trees
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 645-660.

Voir la notice de l'article provenant de la source Library of Science

An [1, k]-set S in a graph G is a dominating set such that every vertex not in S has at most k neighbors in it. If the additional requirement that the set must be independent is added, the existence of such sets is not guaranteed in every graph. In this paper we solve some problems previously posed by other authors about independent [1, 2]-sets. We provide a necessary condition for a graph to have an independent [1, 2]-set, in terms of spanning trees, and we prove that this condition is also sufficient for cactus graphs. We follow the concept of excellent tree and characterize the family of trees such that any vertex belongs to some independent [1, 2]-set. Finally, we describe a linear algorithm to decide whether a tree has an independent [1, 2]-set. This algorithm can be easily modified to obtain the cardinality of a smallest independent [1, 2]-set of a tree.
Keywords: domination, independence, spanning trees, excellent trees 
@article{DMGT_2018_38_3_a3,
     author = {Aleid, Sahar A. and C\'aceres, Jos\'e and Puertas, Mar{\'\i}a Luz},
     title = {On {Independent} [1, {2]-Sets} in {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {645--660},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a3/}
}
TY  - JOUR
AU  - Aleid, Sahar A.
AU  - Cáceres, José
AU  - Puertas, María Luz
TI  - On Independent [1, 2]-Sets in Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 645
EP  - 660
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a3/
LA  - en
ID  - DMGT_2018_38_3_a3
ER  - 
%0 Journal Article
%A Aleid, Sahar A.
%A Cáceres, José
%A Puertas, María Luz
%T On Independent [1, 2]-Sets in Trees
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 645-660
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a3/
%G en
%F DMGT_2018_38_3_a3
Aleid, Sahar A.; Cáceres, José; Puertas, María Luz. On Independent [1, 2]-Sets in Trees. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 645-660. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a3/

[1] T.A. Beyer, A. Proskurowski, S.T. Hedetniemi and S. Mitchell, Independent domination in trees, Congr. Numer. 19 (1997) 321–328.

[2] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 5th edition (CRC Press, 2011).

[3] M. Chellali, S.T. Hedetniemi and A. McRae, [1, 2] -set in graphs, Discrete Appl. Math. 161 (2013) 2885–2893. doi:10.1016/j.dam.2013.06.012

[4] M. Chellali, O. Favaron, T.W. Haynes, S.T. Hedetniemi and A. McRae, Independent [1, k ] -sets in graphs, Australas. J. Combin. 59 (2014) 144–156.

[5] E. Cockayne, S. Goodman and S. Hedetniemi, A linear algorithm for the domination number of a tree, Inform. Process. Lett. 4 (1975) 41–44. doi:10.1016/0020-0190(75)90011-3

[6] G.F. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and R.C. Laskar, Excellent trees, Bull. Inst. Combin. Appl. 34 (2002) 27–38.

[7] J.H. Hattingh and M.A. Henning, Restrained domination excellent trees, Ars Combin. 87 (2008) 337–351.

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

[9] T.W. Haynes and M.A. Henning, A characterization of i-excellent trees, Discrete Math. 248 (2002) 69–77. doi:10.1016/S0012-365X(01)00274-6

[10] M.A. Henning, Total domination excellent trees, Discrete Math. 263 (2003) 93–104. doi:10.1016/S0012-365X(02)00572-1

[11] R. Laskar, J. Pfaff, S.M. Hedetniemi and S.T. Hedetniemi, On the algorithmic complexity of total domination, SIAM J. Algebraic Discrete Methods 5 (1984) 420–425. doi:10.1137/0605040

[12] K.S. Natarajan and L.J. White, Optimum domination in weighted trees, Inform. Process. Lett. 7 (1978) 261–265. doi:10.1016/0020-0190(78)90012-1

[13] S.L. Mitchell and S.T. Hedetniemi, Edge domination in trees, Congr. Numer. 19 (1977) 489–509.

[14] P.J. Slater, R-domination in graphs, J. ACM 23 (1976) 446–450. doi:10.1145/321958.321964

[15] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38 (1980) 364–372. doi:10.1137/0138030