- Tytuł:
- Nordhaus-Gaddum bounds for upper total domination
- Autorzy:
-
Haynes, Teresa W.
Henning, Michael A. - Powiązania:
- https://bibliotekanauki.pl/articles/2216175.pdf
- Data publikacji:
- 2022
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
upper total domination
Nordhaus-Gaddum bound - Opis:
- A set S of vertices in an isolate-free graph G is a total dominating set if every vertex in G is adjacent to a vertex in S. A total dominating set of G is minimal if it contains no total dominating set of $\bar{G}$ as a proper subset. The upper total domination number $Γ_t(G)$ of G is the maximum cardinality of a minimal total dominating set in G. We establish Nordhaus-Gaddum bounds involving the upper total domination numbers of a graph G and its complement $\bar{G}$. We prove that if G is a graph of order n such that both G and $\bar{G}$ are isolate-free, then $Γ_t(G) + Γ_t(\bar{G}) ≤ n + 2$ and $Γ_t(G)Γ_t(\bar{G}) ≤ 1/4 (n + 2)^2$, and these bounds are tight.
- Źródło:
-
Opuscula Mathematica; 2022, 42, 4; 573-582
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł