Geodesic
Domination Number, Independent Domination Number and 2-Independence Number in Trees
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 39-49.

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

For a graph G, let γ(G) be the domination number, i(G) be the independent domination number and β_2(G) be the 2-independence number. In this paper, we prove that for any tree T of order n ≥ 2, 4β_2(T) − 3γ(T) ≥ 3i(T), and we characterize all trees attaining equality. Also we prove that for every tree T of order n ≥ 2, i(T)≤3β_2(T)/4, and we characterize all extreme trees.
Keywords: 2-independence number, domination number, independent domination number 
@article{DMGT_2021_41_1_a1,
     author = {Dehgardi, Nasrin and Sheikholeslami, Seyed Mahmoud and Valinavaz, Mina and Aram, Hamideh and Volkmann, Lutz},
     title = {Domination {Number,} {Independent} {Domination} {Number} and {2-Independence} {Number} in {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {39--49},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a1/}
}
TY  - JOUR
AU  - Dehgardi, Nasrin
AU  - Sheikholeslami, Seyed Mahmoud
AU  - Valinavaz, Mina
AU  - Aram, Hamideh
AU  - Volkmann, Lutz
TI  - Domination Number, Independent Domination Number and 2-Independence Number in Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 39
EP  - 49
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a1/
LA  - en
ID  - DMGT_2021_41_1_a1
ER  - 
%0 Journal Article
%A Dehgardi, Nasrin
%A Sheikholeslami, Seyed Mahmoud
%A Valinavaz, Mina
%A Aram, Hamideh
%A Volkmann, Lutz
%T Domination Number, Independent Domination Number and 2-Independence Number in Trees
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 39-49
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a1/
%G en
%F DMGT_2021_41_1_a1
Dehgardi, Nasrin; Sheikholeslami, Seyed Mahmoud; Valinavaz, Mina; Aram, Hamideh; Volkmann, Lutz. Domination Number, Independent Domination Number and 2-Independence Number in Trees. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 39-49. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a1/

[1] J. Amjadi, N. Dehgardi, S.M. Sheikholeslami and M. Valinavaz, Independent Roman domination and 2- independence in trees, Discrete Math. Algorithms Appl. 10 (2018) 1850052. doi: 10.1142/S1793830918500520

[2] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-domination and k-independence in graphs: A survey, Graphs Combin. 28 (2012) 1–55. doi: 10.1007/s00373-011-1040-3

[3] M. Chellali and N. Meddah, Trees with equal 2-domination and 2-independence numbers, Discuss. Math. Graph Theory 32 (2012) 263–270. doi: 10.7151/dmgt.1603

[4] N. Dehgardi, Mixed Roman domination and 2-independence in trees, Commun. Comb. Optim. 3 (2018) 79–91. doi: 10.22049/CCO.2018.25964.1062

[5] O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combin. Theory Ser. B 39 (1985) 101–102. doi: 10.1016/0095-8956(85)90040-1

[6] O. Favaron, Graduate course in the University of Blida (2005), unpublished.

[7] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science (Wiley, New York, 1985) 283–300.

[8] Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, in: Graph Theory with Applications to Algorithms and Computer Science (Wiley, New York, 1985) 301–311.

[9] A. Hansberg, D. Meierling and L. Volkmann, Independence and k-domination in graphs, Int. J. Comput. Math. 88 (2011) 905–915. doi: 10.1080/00207160.2010.482664

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

[11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998).

[12] M.S. Jacobson, K. Peters and D.F. Rall, On n-irredundance and n-domination, Ars Combin. 29 (1990) 151–160.

[13] N. Meddah and M. Chellali, Roman domination and 2-independence in trees, Discrete Math. Algorithms Appl. 9 (2017) 1750023. doi: 10.1142/S1793830917500239