PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 153-171
Tytuł artykułu

Bounds On The Disjunctive Total Domination Number Of A Tree

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
1
Strony
153-171
Opis fizyczny
Daty
wydano
2016-02-01
poprawiono
2015-05-28
zaakceptowano
2015-05-28
otrzymano
2015-11-14
online
2016-01-19
Twórcy
  • Department of Pure and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa, mahenning@uj.ac.za
  • Department of Pure and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa; and Department of Mathematics, Rhodes University, Grahamstown, 6140 South Africa, v.naicker@ru.ac.za
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1854
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.