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
-
1
Web of Science
-
2
Scopus
Autorzy (5)
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
- Bibliografia: test
-
- M. Blidia, M. Chellali and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, Discrete Math. 306 (2006) 1840-1845. doi:10.1016/j.disc.2006.03.061 otwiera się w nowej karcie
- B. Brešar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian products of graphs, Util. Math. 73 (2007) 255-265. otwiera się w nowej karcie
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North Holland, New York, 1976). otwiera się w nowej karcie
- X.-G. Chen, L. Sun and H.-M. Xing, Paired-domination numbers of cubic graphs, Acta Math. Sci. Ser. A Chin. Ed. 27 (2007) 166-170, in Chinese.
- T.C.E. Cheng, L.Y. Kang and C.T. Ng, Paired domination on interval and circular- arc graphs, Discrete Appl. Math. 155 (2007) 2077-2086. doi:10.1016/j.dam.2007.05.011 otwiera się w nowej karcie
- T.C.E. Cheng, L.Y. Kang and E. Shan, A polynomial-time algorithm for the paired-domination problem on permutation graphs, Discrete Appl. Math. 157 (2009) 262-271. doi:10.1016/j.dam.2008.02.015 otwiera się w nowej karcie
- W.J. Desormeaux, T.W. Haynes, M.A. Henning and A. Yeo, Total domination in graphs with diameter 2, J. Graph Theory 75 (2014) 91-103. doi:10.1002/jgt.21725 otwiera się w nowej karcie
- W.J. Desormeaux and M.A. Henning, Paired domination in graphs: a survey and recent results, Util. Math. 94 (2014) 101-166.
- P. Dorbec and S. Gravier, Paired-domination in P 5 -free graphs, Graphs Combin. 24 (2008) 303-308. doi:10.1007/s00373-008-0792-x otwiera się w nowej karcie
- P. Dorbec, S. Gravier and M.A. Henning, Paired-domination in generalized claw-free graphs, J. Comb. Optim. 14 (2007) 1-7. doi:10.1007/s10878-006-9022-8 otwiera się w nowej karcie
- P. Dorbec, B. Hartnell and M.A. Henning, Paired versus double domination in K 1,r - free graphs, J. Comb. Optim. 27 (2014) 688-694. doi:10.1007/s10878-012-9547-y otwiera się w nowej karcie
- O. Favaron and M.A. Henning, Paired-domination in claw-free cubic graphs, Graphs Combin. 20 (2004) 447-456. doi:10.1007/s00373-004-0577-9 otwiera się w nowej karcie
- J. Cyman, M. Dettlaff, M.A. Henning, M. Lemańska and J. Raczek otwiera się w nowej karcie
- W. Goddard, personal communication at 16th CID Workshop on Graph Theory, September 20-25 (2015) Szklarska Porȩba, Poland. otwiera się w nowej karcie
- W. Goddard and M.A. Henning,, A characterization of cubic graphs with paired- domination number three-fifths their order , Graphs Combin. 25 (2009) 675-692. doi:10.1007/s00373-010-0884-2 otwiera się w nowej karcie
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). otwiera się w nowej karcie
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). otwiera się w nowej karcie
- T.W. Haynes and P.J. Slater, Paired-domination and the paired-domatic number , Congr. Numer. 109 (1995) 65-72. otwiera się w nowej karcie
- T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206. doi:10.1002/(SICI)1097-0037(199810)32:3 199::AID-NET4 3.0.CO;2-F otwiera się w nowej karcie
- M.A. Henning, Graphs with large paired-domination number , J. Comb. Optim. 13 (2007) 61-78. doi:10.1007/s10878-006-9014-8 otwiera się w nowej karcie
- M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009) 32-63. doi:10.1016/j.disc.2007.12.044 otwiera się w nowej karcie
- M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, Springer-Verlag, New York, 2013). otwiera się w nowej karcie
- A.J. Hoffman and R.R. Singleton, On Moore graphs with diameter 2 and 3, IBM J. Res. Dev. 4 (1960) 497-504. doi:10.1147/rd.45.0497 otwiera się w nowej karcie
- O. Schaudt, Total domination versus paired domination, Discuss. Math. Graph The- ory 32 (2012) 435-447. doi:10.7151/dmgt.1614 otwiera się w nowej karcie
- N. Robertson, Graphs Minimal Under Girth, Valency, and Connectivity Constraints (Dissertation, Waterloo, Ontario, University of Waterloo, 1969).
- R.R. Singleton, There is no irregular Moore graph, Amer. Math. Monthly 75 (1968) 42-43. doi:10.2307/2315106 otwiera się w nowej karcie
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 150 razy
Publikacje, które mogą cię zainteresować
Total Domination Versus Domination in Cubic Graphs
- J. Cyman,
- M. Dettlaff,
- M. A. Henning
- + 2 autorów