Bounds on the disjunctive total domination number of a tree
Michael A. Henning, Viroshan Naicker · Discussiones Mathematicae Graph Theory · 2015
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, γ d t (G), is the minimum cardinality of such a set.We observe that γ d t (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 ≤ γ d t (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 )/γ d t (T ) < 2 and this bound is asymptotically tight.