Geodesic
Domination Number of Graphs with Minimum Degree Five
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 763-777

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

We prove that for every graph G on n vertices and with minimum degree five, the domination number γ(G) cannot exceed n/3. The proof combines an algorithmic approach and the discharging method. Using the same technique, we provide a shorter proof for the known upper bound 4n/11 on the domination number of graphs of minimum degree four.
Keywords: dominating set, domination number, discharging method 
Bujtás, Csilla. Domination Number of Graphs with Minimum Degree Five. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 763-777. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a4/
@article{DMGT_2021_41_3_a4,
     author = {Bujt\'as, Csilla},
     title = {Domination {Number} of {Graphs} with {Minimum} {Degree} {Five}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {763--777},
     year = {2021},
     volume = {41},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a4/}
}
TY  - JOUR
AU  - Bujtás, Csilla
TI  - Domination Number of Graphs with Minimum Degree Five
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 763
EP  - 777
VL  - 41
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a4/
LA  - en
ID  - DMGT_2021_41_3_a4
ER  - 
%0 Journal Article
%A Bujtás, Csilla
%T Domination Number of Graphs with Minimum Degree Five
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 763-777
%V 41
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a4/
%G en
%F DMGT_2021_41_3_a4

[1] N. Alon, Transversal numbers of uniform hypergraphs, Graphs Combin. 6 (1990) 1–4. doi:10.1007/BF01787474

[2] 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.

[3] Cs. Biró, É. Czabarka, P. Dankelmann and L. Székely, Remarks on the domination number of graphs, Bull. Inst. Combin. Appl. 64 (2012) 73–83.

[4] 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.

[5] B. Brešar, T. Gologranc, M. Milanič, D.F. Rall and R. Rizzi, Dominating sequences in graphs, Discrete Math. 336 (2014) 22–36. doi:10.1016/j.disc.2014.07.016

[6] B. Brešar, S. Klavžar and D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991. doi:10.1137/100786800

[7] 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. doi:10.1007/s00373-015-1585-7

[8] C.N. Campos, and Y. Wakabayashi, On dominating sets of maximal outerplanar graphs, Discrete Appl. Math. 161 (2013) 330–335. doi:10.1016/j.dam.2012.08.023

[9] 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.

[10] S. Dantas, F. Joos, C. Löwenstein, D.S. Machado and D. Rautenbach, Domination and total domination in cubic graphs of large girth, Discrete Appl. Math. 174 (2014) 128–132. doi:10.1016/j.dam.2014.04.011

[11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[12] M.A. Henning, I. Schiermeyer and A. Yeo, A new bound on the domination number of graphs with minimum degree two, Electron. J. Combin. 18 (2011) #P12. doi:10.37236/499

[13] E.L.C. King and M.J. Pelsmajer, Dominating sets in plane triangulations, Discrete Math. 310 (2010) 2221–2230. doi:10.1016/j.disc.2010.03.022

[14] A.V. Kostochka and B.Y. Stodolsky, On domination in connected cubic graphs, Discrete Math. 304 (2005) 45–50. doi:10.1016/j.disc.2005.07.005

[15] A.V. Kostochka and B.Y. Stodolsky, An upper bound on the domination number of n-vertex connected cubic graphs, Discrete Math. 309 (2009) 1142–1162. doi:10.1016/j.disc.2007.12.009

[16] D. Král, P. Škoda and J. Volec, Domination number of cubic graphs with large girth, J. Graph Theory 69 (2012) 131–142. doi:10.1002/jgt.20568

[17] C. Löwenstein and D. Rautenbach, Domination in graphs of minimum degree at least two and large girth, Graphs Combin. 24 (2008) 37–46. doi:10.1007/s00373-007-0770-8

[18] W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749–762. doi:10.1002/jgt.3190130610

[19] O. Ore, Theory of Graphs (A.M.S., Providence, R.I., 1962). doi:10.1090/coll/038

[20] C. Payan, Sur le nombre d’absorption d’un graphe simple, Cahiers CentreÉtudes Recherche Opér. 17 (1975) 307–317.

[21] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277–295. doi:10.1017/S0963548300002042

[22] M.-Y. Sohn and Y. Xudong, Domination in graphs of minimum degree four, J. Korean Math. Soc. 46 (2009) 759–773. doi:10.4134/JKMS.2009.46.4.759

[23] H.-M. Xing, L. Sun and X.-G. Chen, Domination in graphs of minimum degree five, Graphs Combin. 22 (2006) 127–143. doi:10.1007/s00373-006-0638-3