- Tytuł:
- Total Domination Versus Paired-Domination in Regular Graphs
- Autorzy:
-
Cyman, Joanna
Dettlaff, Magda
Henning, Michael A.
Lemańska, Magdalena
Raczek, Joanna - Powiązania:
- https://bibliotekanauki.pl/articles/31342314.pdf
- Data publikacji:
- 2018-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination
total domination
paired-domination - Opis:
- A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, γt(G), and the paired-domination number, γpr(G), respectively. For k ≥ 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447] that γpr(G)/γt(G) ≤ (2k)/(k+1). In the special case when k = 2, we observe that γpr(G)/γt(G) ≤ 4/3, with equality if and only if G ≅ C5. When k = 3, we show that γpr(G)/γt(G) ≤ 3/2, with equality if and only if G is the Petersen graph. More generally for k ≥ 2, if G has girth at least 5 and satisfies γpr(G)/γt(G) = (2k)/(k + 1), then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k ≥ 2 and k ≠ 57, if G has girth at least 5, then γpr(G)/γt(G) ≤ (2k)/(k +1), with equality if and only if k = 2 and G ≅ C5 or k = 3 and G is the Petersen graph.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 573-586
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł