- Tytuł:
- Bounds On The Disjunctive Total Domination Number Of A Tree
- Autorzy:
-
Henning, Michael A.
Naicker, Viroshan - Powiązania:
- https://bibliotekanauki.pl/articles/31341124.pdf
- Data publikacji:
- 2016-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
total domination
disjunctive total domination
trees - Opis:
- 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_t^d (G) $, is the minimum cardinality of such a set. We observe that $ \gamma_t^d (G) \ge \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 $ \mathcal{l} $ leaves and $s$ support vertices, then $ 2(n−\mathcal{l}+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 $ \gamma_t(T) // \gamma_t^d (T) <2 $ and this bound is asymptotically tight.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 153-171
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł