Bounds On The Disjunctive Total Domination Number Of A Tree

Michael A. Henning, and Viroshan Naicker. "Bounds On The Disjunctive Total Domination Number Of A Tree." Discussiones Mathematicae Graph Theory 36.1 (2016): 153-171. <http://eudml.org/doc/276970>.

@article{MichaelA2016,
abstract = {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.},
author = {Michael A. Henning, Viroshan Naicker},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {total domination; disjunctive total domination; trees},
language = {eng},
number = {1},
pages = {153-171},
title = {Bounds On The Disjunctive Total Domination Number Of A Tree},
url = {http://eudml.org/doc/276970},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Michael A. Henning
AU - Viroshan Naicker
TI - Bounds On The Disjunctive Total Domination Number Of A Tree
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 153
EP - 171
AB - 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.
LA - eng
KW - total domination; disjunctive total domination; trees
UR - http://eudml.org/doc/276970
ER -