Geodesic
Bounds on Domination Parameters in Graphs: A Brief Survey
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 665-708.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2022_42_3_a0,
     author = {Henning, Michael A.},
     title = {Bounds on {Domination} {Parameters} in {Graphs:} {A} {Brief} {Survey}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {665--708},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a0/}
}
TY  - JOUR
AU  - Henning, Michael A.
TI  - Bounds on Domination Parameters in Graphs: A Brief Survey
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 665
EP  - 708
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a0/
LA  - en
ID  - DMGT_2022_42_3_a0
ER  - 
%0 Journal Article
%A Henning, Michael A.
%T Bounds on Domination Parameters in Graphs: A Brief Survey
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 665-708
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a0/
%G en
%F DMGT_2022_42_3_a0
Henning, Michael A. Bounds on Domination Parameters in Graphs: A Brief Survey. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 665-708. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a0/

[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 Gra ti.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 irredun-dance, 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