BOUNDS ON THE DISJUNCTIVE TOTAL DOMINATION NUMBER OF A TREE

作者：Henning Michael A^*; Naicker Viroshan

来源：Discussiones Mathematicae - Graph Theory, 2016, 36(1): 153-171.

DOI：10.7151/dmgt.1854

• total domination
• disjunctive total domination
• trees

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, gamma(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, gamma(d)(t)(G)), is the minimum cardinality of such a set. We observe that gamma(d)(t)(G) <= 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 l leaves and s support vertices, then 2(n - l + 3)/5 <= gamma(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 gamma(t)(T)/gamma(d)(t)(T) < 2 and this bound is asymptotically tight.

• 出版日期2016