- 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ł