Bounds On The Disjunctive Total Domination Number Of A Tree

• Autorzy: Michael A. Henning , Viroshan Naicker
• Języki publikacji: EN

Abstrakty

EN

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) $\gamma _t^d (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G) $\gamma _t^d (G) \le \gamma _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 $2(n - \ell + 3)/5 \le \gamma _t^d (T) \le (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 $\gamma _t (T)/\gamma _t^d (T) < 2$ and this bound is asymptotically tight.

Słowa kluczowe

EN

total domination; disjunctive total domination; trees

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 153-171

Daty

wydano

2016-02-01

poprawiono

2015-05-28

zaakceptowano

2015-05-28

otrzymano

2015-11-14

online

2016-01-19

Twórcy

autor

Michael A. Henning

• Department of Pure and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa

autor

Viroshan Naicker

• Department of Pure and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa; and Department of Mathematics, Rhodes University, Grahamstown, 6140 South Africa

Bibliografia

• [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]
• [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[WoS][Crossref]
• [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[Crossref]
• [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]
• [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]
• [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]
• [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]
• [14] Zs. Tuza, Covering all cliques of a graph, Discrete Math. 86 (1990) 117–126. doi:10.1016/0012-365X(90)90354-K[Crossref]

Identyfikatory

DOI

10.7151/dmgt.1854