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, [...] γtd(G) , is the minimum cardinality of such a set. We observe that [...] γtd(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≤γtd(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)/γtd(T)<2 and this bound is asymptotically tight.
@article{bwmeta1.element.doi-10_7151_dmgt_1854,
author = {Michael A. Henning and Viroshan Naicker},
title = {Bounds On The Disjunctive Total Domination Number Of A Tree},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {153-171},
zbl = {1329.05233},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1854}
}
Michael A. Henning; Viroshan Naicker. Bounds On The Disjunctive Total Domination Number Of A Tree. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 153-171. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1854/
[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[Crossref] | Zbl 1041.05057
[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. | Zbl 0958.05100
[3] V. Chvátal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19–26. doi:10.1007/BF01191201[WoS][Crossref] | Zbl 0776.05080
[4] M. Chellali and T.W. Haynes, Total and paired-domination numbers of a tree, AKCE Int. J. Graphs Comb. 1 (2004) 69–75. | Zbl 1066.05101
[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. | Zbl 1114.05071
[6] F. Chung, Graph theory in the information age, Notices Amer. Math. Soc. 57 (2010) 726–732. | Zbl 1274.05461
[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[Crossref] | Zbl 0447.05039
[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[Crossref] | Zbl 1300.05220
[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[Crossref][WoS]
[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[Crossref] | Zbl 0959.05089
[11] M.A. Henning and V. Naicker, Disjunctive total domination in graphs, J. Comb. Optim., to appear. doi:10.1007/s10878-014-9811-4[Crossref] | Zbl 1336.05102
[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[Crossref] | Zbl 06150331
[14] Zs. Tuza, Covering all cliques of a graph, Discrete Math. 86 (1990) 117–126. doi:10.1016/0012-365X(90)90354-K[Crossref]