Geodesic
Bounds On The Disjunctive Total Domination Number Of A Tree
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 153-171.

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

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γ_t(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, γ_t^d (G), is the minimum cardinality of such a set. We observe that γ_t^d (G) ≥γ_t (G). A leaf of G is a vertex of degree 1, while a support vertex of G is a vertex adjacent to a leaf. We show that if T is a tree of order n with 𝓁 leaves and s support vertices, then 2(n−𝓁+3) // 5 ≤γ_t^d (T) ≤ (n+s−1)//2 and we characterize the families of trees which attain these bounds. For every tree T, we show have γ_t(T) // γ_t^d (T) lt;2 and this bound is asymptotically tight.
Keywords: total domination, disjunctive total domination, trees 
@article{DMGT_2016_36_1_a11,
     author = {Henning, Michael A. and Naicker, Viroshan},
     title = {Bounds {On} {The} {Disjunctive} {Total} {Domination} {Number} {Of} {A} {Tree}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {153--171},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a11/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Naicker, Viroshan
TI  - Bounds On The Disjunctive Total Domination Number Of A Tree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 153
EP  - 171
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a11/
LA  - en
ID  - DMGT_2016_36_1_a11
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Naicker, Viroshan
%T Bounds On The Disjunctive Total Domination Number Of A Tree
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 153-171
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a11/
%G en
%F DMGT_2016_36_1_a11
Henning, Michael A.; Naicker, Viroshan. Bounds On The Disjunctive Total Domination Number Of A Tree. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 153-171. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a11/

[1] D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei and R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207–210. doi:10.1002/jgt.20000

[2] R.C. Brigham, J.R. Carrington and R.P. Vitray, Connected graphs with maximum total domination number, J. Combin. Math. Combin. Comput. 34 (2000) 81–96.

[3] V. Chvátal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19–26. doi:10.1007/BF01191201

[4] M. Chellali and T.W. Haynes, Total and paired-domination numbers of a tree, AKCE Int. J. Graphs Comb. 1 (2004) 69–75.

[5] M. Chellali and T.W. Haynes, A note on the total domination number of a tree, J. Combin. Math. Combin. Comput. 58 (2006) 189–193.

[6] F. Chung, Graph theory in the information age, Notices Amer. Math. Soc. 57 (2010) 726–732.

[7] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219. doi:10.1002/net.3230100304

[8] W. Goddard, M.A. Henning and C.A. McPillan, The disjunctive domination number of a graph, Quaest. Math. 37 (2014) 547–561. doi:10.2989/16073606.2014.894688

[9] M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009) 32–63. doi:10.1016/j.disc.2007.12.044

[10] M.A. Henning, Graphs with large total domination number, J. Graph Theory 35 (2000) 21–45. doi:10.1002/1097-0118(200009)35:1〈21::AID-JGT3〉3.0.CO;2-F

[11] M.A. Henning and V. Naicker, Disjunctive total domination in graphs, J. Comb. Optim., to appear. doi:10.1007/s10878-014-9811-4

[12] M.A. Henning and V. Naicker, Graphs with large disjunctive total domination number, Discrete Math. Theoret. Comput. Sci. 17 (2015) 255–282.

[13] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). doi:10.1007/978-1-4614-6525-6

[14] Zs. Tuza, Covering all cliques of a graph, Discrete Math. 86 (1990) 117–126. doi:10.1016/0012-365X(90)90354-K