DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

M.A. Henning

Michael A. Henning

University of Johannesburg

email: mahenning@uj.ac.za

0000-0001-8185-067X

Title:

Bounds on domination parameters in graphs: a brief survey

PDF

Source:

Discussiones Mathematicae Graph Theory 42(3) (2022) 665-708

Received: 2022-02-05 , Revised: 2022-03-29 , Accepted: 2022-03-29 , Available online: 2022-04-28 , https://doi.org/10.7151/dmgt.2454

Abstract:

In this paper we present a brief survey of bounds on selected domination parameters. We focus primarily on bounds on domination parameters in terms of the order and minimum degree of the graph. We present a list of open problems and conjectures that have yet to be solved in the hope of attracting future researchers to the field.

Keywords:

bounds, domination parameters

References:

  1. N. Alon, Transversal numbers of uniform hypergraphs, Graphs Combin. 6 (1990) 1–4.
    https://doi.org/10.1007/BF01787474
  2. D. Archdeacon, J. Ellis-Monaghan, D. Fisher, D. Froncek, P.C.B. Lam, S. Seager, B. Wei and R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207–210.
    https://doi.org/10.1002/jgt.20000
  3. V.I. Arnautov, Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices, Prikl. Mat. i Programmirovanie 11 (1974) 3–8, in Russian.
  4. C. Berge, Graphs and Hypergraphs (North-Holland Publishing Company, Amsterdam-London, 1973).
  5. M.M. Blank, An estimate of the external stability number of a graph without suspended vertices, Prikl. Mat. i Programmirovanie 10 (1973) 3–11, in Russian.
  6. A. Blumenthal, Domination Problems in Directed Graphs and Inducibility of Nets, Ph.D Thesis (Iowa State University, 2020).
  7. B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249.
    https://doi.org/10.1002/jgt.3190030306
  8. R.C. Brigham, J.R. Carrington and R.P. Vitray, Connected graphs with maximum total domination number, J. Combin. Comput. Combin. Math. 34 (2000) 81–96.
  9. Cs. Bujtás, Domination number of graphs with minimum degree five, Discuss. Math. Graph Theory 41 (2021) 763–777.
    https://doi.org/10.7151/dmgt.2339
  10. Cs. Bujtás and M.A. Henning, On the domination number of graphs with minimum degree six, Discrete Math. 344 (2021) 112449.
    https://doi.org/10.1016/j.disc.2021.112449
  11. Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62–71.
    https://doi.org/10.1016/j.ejc.2011.08.002
  12. Cs. Bujtás and S. Klavžar, Improved upper bounds on the domination number of graphs with minimum degree at least five, Graphs Combin. 32 (2016) 511–519.
    https://doi.org/10.1007/s00373-015-1585-7
  13. Y. Caro, D.B. West and R. Yuster, Connected domination and spanning trees with many leaves, SIAM J. Discrete Math. 13 (2000) 202–211.
    https://doi.org/10.1137/S0895480199353780
  14. X.G. Chen, L. Sun and H.M. Xing, Paired domination numbers of cubic graphs, Acta Math. Sci. Ser. A (Chinese Ed.) 27 (2007) 166–170, in Chinese.
  15. E.-K. Cho, I. Choi and B. Park, On independent domination in regular graphs (2021).
    arXiv: 2107.00295
  16. V. Chvátal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19–26.
    https://doi.org/10.1007/BF01191201
  17. W.E. Clark, B. Shekhtman, S. Suen and D.C. Fisher, Upper bounds for the domination number of a graph, Congr. Numer. 132 (1998) 99–123.
  18. E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219.
    https://doi.org/10.1002/net.3230100304
  19. P. Dankelmann, D. Day, J.H. Hattingh, M.A. Henning, L.R. Markus and H.C. Swart, On equality in an upper bound for the restrained and total domination numbers of a graph, Discrete Math. 307 (2007) 2845–2852.
    https://doi.org/10.1016/j.disc.2007.03.003
  20. E. DeLaViña, Q. Liu, R. Pepper, B. Waller and D.B. West, Some conjectures of Graffiti.pc on total domination, in: Proceedings of the Thirty-Eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 185 (2007) 81–95.
  21. W.J. Desormeaux and M.A. Henning, Paired domination in graphs: A survey and recent results, Util. Math. 94 (2014) 101–166.
  22. G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar and L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61–69.
    https://doi.org/10.1016/S0012-365X(99)00016-3
  23. G.S. Domke, J.H. Hattingh, M.A. Henning and L.R. Markus, Restrained domination in graphs with minimum degree two, J. Combin. Math. Combin. Comput. 35 (2000) 239–254.
  24. A. Eustis, M.A. Henning and A. Yeo, Independence in $5$-uniform hypergraphs, Discrete Math. 339 (2016) 1004–1027.
    https://doi.org/10.1016/j.disc.2015.10.034
  25. O. Favaron, Two relations between the parameters of independence and irredundance, Discrete Math. 70 (1988) 17–20.
    https://doi.org/10.1016/0012-365X(88)90076-3
  26. N.I. Glebov and A.V. Kostochka, On the independent domination number of graphs with given minimum degree, Discrete Math. 188 (1998) 261–266.
    https://doi.org/10.1016/S0012-365X(97)00267-7
  27. 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.
    https://doi.org/10.1007/s00373-010-0884-2
  28. W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854.
    https://doi.org/10.1016/j.disc.2012.11.031
  29. W. Goddard, M.A. Henning, J. Lyle and J. Southey, On the independent domination number of regular graphs, Ann. Comb. 16 (2012) 719–732.
    https://doi.org/10.1007/s00026-012-0155-4
  30. W. Goddard, M.A. Henning and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014) 67–81.
  31. J.R. Griggs and M. Wu, Spanning trees in graphs of minimum degree $4$ or $5$, Discrete Math. 104 (1992) 167–183.
    https://doi.org/10.1016/0012-365X(92)90331-9
  32. J.H. Hattingh and E.J. Joubert, Restrained domination in cubic graphs, J. Comb. Optim. 22 (2011) 166–179.
    https://doi.org/10.1007/s10878-009-9281-2
  33. T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Eds), Topics in Domination in Graphs (Developments in Mathematics 64, Springer, Cham, 2020).
    https://doi.org/10.1007/978-3-030-51117-3
  34. T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Eds), Structures of Domination in Graphs (Developments in Mathematics 66, Springer, Cham, 2021).
    https://doi.org/10.1007/978-3-030-58892-2
  35. T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Eds), Domination in Graphs: Core Concepts, Developments in Mathematics, Springer, Cham, to appear.
  36. T.W. Haynes and M.A. Henning, Semipaired domination in graphs, J. Combin. Math. Combin. Comput. 104 (2018) 93–109.
  37. T.W. Haynes and M.A. Henning, Graphs with large semipaired domination number, Discuss. Math. Graph Theory 39 (2019) 659–671.
    https://doi.org/10.7151/dmgt.2143
  38. T.W. Haynes and M.A. Henning, Bounds on the semipaired domination number of graphs with minimum degree at least two, J. Comb. Optim. 41 (2021) 451–486.
    https://doi.org/10.1007/s10878-020-00687-w
  39. T.W. Haynes and P.J. Slater, Paired domination in graphs, Networks 32 (1998) 199–206.
    https://doi.org/10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F
  40. S.T. Hedetniemi and R. Laskar, Connected domination in graphs, in: Graph Theory and Combinatorics, Cambridge, 1983, (Academic Press, London 1984) 209–217.
  41. M.A. Henning, Graphs with large restrained domination number, Discrete Math. 197/198 (1999) 415–429.
    https://doi.org/10.1016/S0012-365X(99)90095-X
  42. M.A. Henning, Graphs with large total domination number, J. Graph Theory 35 (2000) 21–45.
    https://doi.org/10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F
  43. M.A. Henning, Graphs with large paired domination number, J. Comb. Optim. 13 (2007) 61–78.
    https://doi.org/10.1007/s10878-006-9014-8
  44. M.A. Henning, Essential upper bounds on the total domination number, Discrete Appl. Math. 244 (2018) 103–115.
    https://doi.org/10.1016/j.dam.2018.03.008
  45. M.A. Henning and N. Jafari Rad, A note on improved upper bounds on the transversal number of hypergraphs, Discrete Math. Algorithms Appl. 11(1) (2019) 1950004.
    https://doi.org/10.1142/S1793830919500046
  46. M.A. Henning and J.E. Maritz, Total restrained domination in graphs with minimum degree two, Discrete Math. 308 (2008) 1909–1920.
    https://doi.org/10.1016/j.disc.2007.04.039
  47. M.A. Henning, M. Pilśniak and E. Tumidajewicz, Bounds on the paired domination number of graphs with minimum degree at least three, Appl. Math. Comput. 417 (2022) 126782.
    https://doi.org/10.1016/j.amc.2021.126782
  48. M.A. Henning and A. Yeo, A transition from total domination in graphs to transversals in hypergraphs, Quaest. Math. 30 (2007) 417–436.
    https://doi.org/10.2989/16073600709486210
  49. M.A. Henning and A. Yeo, Hypergraphs with large transversal number and with edge sizes at least three, J. Graph Theory 59 (2008) 326–348.
    https://doi.org/10.1002/jgt.20340
  50. M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, Springer, New York, 2013).
    https://doi.org/10.1007/978-1-4614-6525-6
  51. M.A. Henning and A. Yeo, The domination number of a random graph, Util. Math. 94 (2014) 315–328.
  52. M.A. Henning and A. Yeo, A new upper bound on the total domination number in graphs with minimum degree six, Discrete Appl. Math. 302 (2021) 1–7.
    https://doi.org/10.1016/j.dam.2021.05.033
  53. M.A. Henning and A. Yeo, Transversals in $6$-uniform hypergraphs and total domination in graphs with minimum degree six, manuscript.
  54. S. Huang and E. Shan, A note on the upper bound for the paired domination number of a graph with minimum degree at least two, Networks 57 (2011) 115–116.
    https://doi.org/10.1002/net.20390
  55. N. Jafari Rad, New probabilistic upper bounds on the domination number of a graph, Electron. J. Combin. 26(3) (2019) #P3.28.
    https://doi.org/10.37236/8345
  56. E.J. Joubert, On a conjecture involving a bound for the total restrained domination number of a graph, Discrete Appl. Math. 258 (2019) 177–187.
    https://doi.org/10.1016/j.dam.2018.11.019
  57. A. Kelmans, Counterexamples to the cubic graph domination conjecture (2006).
    arXiv: math/0607512
  58. D.J. Kleitman and D.B. West, Spanning trees with many leaves, SIAM J. Discrete Math. 4 (1991) 99–106.
    https://doi.org/10.1137/0404010
  59. A.V. Kostochka and B.Y. Stodolsky, On domination in connected cubic graphs, Discrete Math. 304 (2005) 45–50.
    https://doi.org/10.1016/j.disc.2005.07.005
  60. A.V. Kostochka and B.Y. Stodolsky, A new bound on the domination number of connected cubic graphs, Sib. Èlektron. Mat. Izv. 6 (2009) 465–504.
  61. P.C.B. Lam, W.C. Shiu and L. Sun, On independent domination number of regular graphs, Discrete. Math. 202 (1999) 135–144.
    https://doi.org/10.1016/S0012-365X(98)00350-1
  62. W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749–762.
    https://doi.org/10.1002/jgt.3190130610
  63. O. Ore, Theory of graphs, Amer. Math. Soc. Transl. 38 (1962) 206–212.
    https://doi.org/10.1090/coll/038
  64. C. Payan, Sur le nombre d'absorption d'un graphe simple, Cahiers Centre Études Rech. Opér. 17 (1975) 307–317, in French.
  65. C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23–32.
    https://doi.org/10.1002/jgt.3190060104
  66. B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277–295.
    https://doi.org/10.1017/S0963548300002042
  67. M. Rosenfeld, Independent sets in regular graphs, Israel J. Math. 2 (1964) 262–272.
    https://doi.org/10.1007/BF02759743
  68. M.Y. Sohn and Y. Xudong, Domination in graphs of minimum degree four, J. Korean Math. Soc. 46 (2009) 759–773.
    https://doi.org/10.4134/JKMS.2009.46.4.759
  69. L. Sun, An upper bound for the total domination number, J. Beijing Inst. Tech. 4 (1995) 111–114.
  70. L. Sun and J. Wang, An upper bound for the independent domination number, J. Combin. Theory Ser. B 76 (1999) 240–246.
    https://doi.org/10.1006/jctb.1999.1907
  71. S. Thomassé and A. Yeo, Total domination of graphs and small transversals of hypergraphs, Combinatorica 27 (2007) 473–487.
    https://doi.org/10.1007/s00493-007-2020-3
  72. Zs. Tuza, Covering all cliques of a graph, Discrete Math. 86 (1990) 117–126.
    https://doi.org/10.1016/0012-365X(90)90354-K
  73. H.B. Walikar, B.D. Acharya and E. Sampathkumar, Recent Developments in the Theory of Domination in Graphs (Lecture Notes Math. 1, Mehta Research Institute, Allahabad, 1979).
  74. H.M. Xing, L. Sun and X.G. Chen, Domination in graphs of minimum degree five, Graphs Combin. 22 (2006) 127–143.
    https://doi.org/10.1007/s00373-006-0638-3
Close