Temat: upper total domination - Katalog OPAC zbiorów

Skocz do pozycji: 1.

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ł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: Total domination versus paired domination
Autorzy:: Schaudt, Oliver
Powiązania:: https://bibliotekanauki.pl/articles/743224.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: total domination
upper total domination
paired domination
upper paired domination
generalized claw-free graphs
Opis:: A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ.
In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_{1,r}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 2 - 2/(Δ+1), where Δ is the maximum degree. We also show for each r ≥ 2 that ${C₅,T_r}$-free graphs fulfill the sharp bound γₚ/γₜ ≤ 2 - 2/r, where $T_r$ is obtained from $K_{1,r}$ by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_{1,r}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.
Źródło:: Discussiones Mathematicae Graph Theory; 2012, 32, 3; 435-447
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "upper total domination" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język