Total domination in versus paired-domination in regular graphs - Publication - Bridge of Knowledge

Search

Total domination in versus paired-domination in regular graphs

Abstract

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.

Citations

  • 1

    CrossRef

  • 0

    Web of Science

  • 2

    Scopus

Cite as

Full text

download paper
downloaded 143 times
Publication version
Accepted or Published Version
License
Creative Commons: CC-BY-NC-ND open in new tab

Keywords

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
Discussiones Mathematicae Graph Theory no. 38, pages 573 - 586,
ISSN: 1234-3099
Language:
English
Publication year:
2018
Bibliographic description:
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:
Digital Object Identifier (open in new tab) 10.7151/dmgt.2026
Bibliography: 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 open in new tab
  2. B. Brešar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian products of graphs, Util. Math. 73 (2007) 255-265. open in new tab
  3. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North Holland, New York, 1976). open in new tab
  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 open in new tab
  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 open in new tab
  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 open in new tab
  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 open in new tab
  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 open in new tab
  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 open in new tab
  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 open in new tab
  13. J. Cyman, M. Dettlaff, M.A. Henning, M. Lemańska and J. Raczek open in new tab
  14. W. Goddard, personal communication at 16th CID Workshop on Graph Theory, September 20-25 (2015) Szklarska Porȩba, Poland. open in new tab
  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 open in new tab
  16. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). open in new tab
  17. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). open in new tab
  18. T.W. Haynes and P.J. Slater, Paired-domination and the paired-domatic number , Congr. Numer. 109 (1995) 65-72. open in new tab
  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 open in new tab
  20. M.A. Henning, Graphs with large paired-domination number , J. Comb. Optim. 13 (2007) 61-78. doi:10.1007/s10878-006-9014-8 open in new tab
  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 open in new tab
  22. M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, Springer-Verlag, New York, 2013). open in new tab
  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 open in new tab
  24. O. Schaudt, Total domination versus paired domination, Discuss. Math. Graph The- ory 32 (2012) 435-447. doi:10.7151/dmgt.1614 open in new tab
  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 open in new tab
Verified by:
Gdańsk University of Technology

seen 169 times

Recommended for you

Meta Tags