A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a tower of 2’s of height about 1014. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.
@article{bwmeta1.element.doi-10_2478_s11533-014-0449-3,
author = {Teresa Haynes and Michael Henning and Lucas Merwe and Anders Yeo},
title = {A maximum degree theorem for diameter-2-critical graphs},
journal = {Open Mathematics},
volume = {12},
year = {2014},
pages = {1882-1889},
zbl = {1297.05074},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-014-0449-3}
}
Teresa Haynes; Michael Henning; Lucas Merwe; Anders Yeo. A maximum degree theorem for diameter-2-critical graphs. Open Mathematics, Tome 12 (2014) pp. 1882-1889. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-014-0449-3/
[1] J. A. Bondy and U. S. R. Murty, Extremal graphs of diameter two with prescribed minimum degree. Studia Sci. Math. Hungar. 7 (1972), 239–241. | Zbl 0277.05132
[2] L. Caccetta and R. Häggkvist, On diameter critical graphs. Discrete Math. 28 (1979), no. 3, 223–229. http://dx.doi.org/10.1016/0012-365X(79)90129-8 | Zbl 0421.05042
[3] Ya-Chen Chen and Z. Füredi, Minimum vertex-diameter-2-critical graphs. J. Graph Theory 50 (2005), no. 4, 293–315. http://dx.doi.org/10.1002/jgt.20111 | Zbl 1076.05045
[4] P. Erdös and A. Hajnal, Ramsey-type theorems. Discrete Appl. Math. 25 (1989), 37–52. http://dx.doi.org/10.1016/0166-218X(89)90045-0
[5] G. Fan, On diameter 2-critical graphs. Discrete Math. 67 (1987), 235–240. http://dx.doi.org/10.1016/0012-365X(87)90174-9
[6] Z. Füredi, The maximum number of edges in a minimal graph of diameter 2. J. Graph Theory 16 (1992), 81–98. http://dx.doi.org/10.1002/jgt.3190160110 | Zbl 0773.05063
[7] D. Hanson and P. Wang, A note on extremal total domination edge critical graphs. Util. Math. 63 (2003), 89–96. | Zbl 1035.05063
[8] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York (1998). | Zbl 0890.05002
[9] T. W. Haynes and M. A. Henning, A characterization of diameter-2-critical graphs with no antihole of length four. Cent. Eur. J. Math. 10(3) (2012), 1125–1132. http://dx.doi.org/10.2478/s11533-012-0022-x | Zbl 1239.05055
[10] T. W. Haynes, M. A. Henning, L. C. van der Merwe and A. Yeo, On a conjecture of Murty and Simon on diameter two critical graphs. Discrete Math. 311 (2011), 1918–1924. http://dx.doi.org/10.1016/j.disc.2011.05.007 | Zbl 1223.05050
[11] T. W. Haynes, M. A. Henning and A. Yeo, A proof of a conjecture on diameter two critical graphs whose complements are claw-free. Discrete Optim. 8 (2011), 495–501. http://dx.doi.org/10.1016/j.disopt.2011.04.003 | Zbl 1236.05147
[12] T. W. Haynes, M. A. Henning, and A. Yeo, On a conjecture of Murty and Simon on diameter two critical graphs II. Discrete Math. 312 (2012), 315–323. http://dx.doi.org/10.1016/j.disc.2011.09.022 | Zbl 1232.05066
[13] T. W. Haynes, C. M. Mynhardt and L. C. van der Merwe, Total domination edge critical graphs. Util. Math. 54 (1998), 229–240. | Zbl 0918.05069
[14] M. A. Henning, Recent results on total domination in graphs: A survey. Discrete Math. 309 (2009), 32–63. http://dx.doi.org/10.1016/j.disc.2007.12.044 | Zbl 1219.05121
[15] W. Mantel, Wiskundige Opgaven 10 (1906), 60–61.
[16] U. S. R. Murty, On critical graphs of diameter 2. Math. Mag. 41 (1968), 138–140. http://dx.doi.org/10.2307/2688184 | Zbl 0167.22102
[17] J. Plesník, Critical graphs of given diameter. Acta F.R.N Univ Comen Math 30 (1975), 71–93. | Zbl 0318.05115
[18] B. Reed and N. Sbihi, Recognizing bull-free perfect graphs. Graphs Combin. 11 (1995), 171–178. http://dx.doi.org/10.1007/BF01929485 | Zbl 0832.05039
[19] P. Turán, Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436–452. | Zbl 0026.26903
[20] L. C. van der Merwe, Total Domination Critical Graphs, Ph.D. Dissertation, University of South Africa (1998). | Zbl 0918.05069