Wyszukiwarka
Abstrakt
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, \gt(G), and the paired-domination number, \gp(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 \gpr(G)/γt(G) \le (2 k)/(k + 1). In the special case when k = 2, we observe that \gpr(G)/γt(G) \le 4/3, with equality if and only if G \cong C5. When k = 3, we show that \gpr(G)/γt(G) \le 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 \gpr(G)/γt(G) = (2 k)/(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 \ne 57, if G has girth at least 5, then \gpr(G)/γt(G) \le (2 k)/(k + 1), with equality if and only if k=2 and G \cong C5 or k = 3 and G is the Petersen graph.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Autorzy (5)
-
Michael A. Henning
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
Discussiones Mathematicae Graph Theory
nr 38,
strony 573 - 586,
ISSN: 1234-3099 - Język:
- angielski
- Rok wydania:
- 2018
- Opis bibliograficzny:
- Cyman J., Dettlaff M., Henning M. A., Lemańska M., Raczek J.: Total domination in versus paired-domination in regular graphs// Discussiones Mathematicae Graph Theory. -Vol. 38, (2018), s.573-586
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2026
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 233 razy
Publikacje, które mogą cię zainteresować
Total Domination Versus Domination in Cubic Graphs
- J. Cyman,
- M. Dettlaff,
- M. A. Henning
- + 2 autorów