Total domination in versus paired-domination in regular graphs - Publikacja - MOST Wiedzy

Twoje konto

zaloguj

Wyszukiwarka

Total domination in versus paired-domination in regular graphs

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ść

pobierz publikację
pobrano 122 razy
Wersja publikacji
Accepted albo Published Version
Licencja
Creative Commons: CC-BY-NC-ND 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
  1. 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
  2. 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
  3. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North Holland, New York, 1976). otwiera się w nowej karcie
  4. 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.
  5. 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
  6. 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
  7. 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
  8. W.J. Desormeaux and M.A. Henning, Paired domination in graphs: a survey and recent results, Util. Math. 94 (2014) 101-166.
  9. 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
  10. 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
  11. 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
  12. 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
  13. J. Cyman, M. Dettlaff, M.A. Henning, M. Lemańska and J. Raczek otwiera się w nowej karcie
  14. W. Goddard, personal communication at 16th CID Workshop on Graph Theory, September 20-25 (2015) Szklarska Porȩba, Poland. otwiera się w nowej karcie
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, Springer-Verlag, New York, 2013). otwiera się w nowej karcie
  23. 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
  24. 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
  25. N. Robertson, Graphs Minimal Under Girth, Valency, and Connectivity Constraints (Dissertation, Waterloo, Ontario, University of Waterloo, 1969).
  26. 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ć

On trees attaining an upper bound on the total domination number

2015

On the ratio between 2-domination and total outer-independent domination numbers of trees

2013

Total Domination Versus Domination in Cubic Graphs

2018

On trees with double domination number equal to total domination number plus one

2011
Meta Tagi