# A maximum degree theorem for diameter-2-critical graphs

Teresa Haynes; Michael Henning; Lucas Merwe; Anders Yeo

Open Mathematics (2014)

- Volume: 12, Issue: 12, page 1882-1889
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topTeresa Haynes, et al. "A maximum degree theorem for diameter-2-critical graphs." Open Mathematics 12.12 (2014): 1882-1889. <http://eudml.org/doc/268952>.

@article{TeresaHaynes2014,

abstract = {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.},

author = {Teresa Haynes, Michael Henning, Lucas Merwe, Anders Yeo},

journal = {Open Mathematics},

keywords = {Diameter critical; Diameter-2-critical; Total domination critical; diameter critical; diameter-2-critical; total domination critical},

language = {eng},

number = {12},

pages = {1882-1889},

title = {A maximum degree theorem for diameter-2-critical graphs},

url = {http://eudml.org/doc/268952},

volume = {12},

year = {2014},

}

TY - JOUR

AU - Teresa Haynes

AU - Michael Henning

AU - Lucas Merwe

AU - Anders Yeo

TI - A maximum degree theorem for diameter-2-critical graphs

JO - Open Mathematics

PY - 2014

VL - 12

IS - 12

SP - 1882

EP - 1889

AB - 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.

LA - eng

KW - Diameter critical; Diameter-2-critical; Total domination critical; diameter critical; diameter-2-critical; total domination critical

UR - http://eudml.org/doc/268952

ER -

## References

top- [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. Zbl0277.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 Zbl0421.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 Zbl1076.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 Zbl0773.05063
- [7] D. Hanson and P. Wang, A note on extremal total domination edge critical graphs. Util. Math. 63 (2003), 89–96. Zbl1035.05063
- [8] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York (1998). Zbl0890.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 Zbl1239.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 Zbl1223.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 Zbl1236.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 Zbl1232.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. Zbl0918.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 Zbl1219.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 Zbl0167.22102
- [17] J. Plesník, Critical graphs of given diameter. Acta F.R.N Univ Comen Math 30 (1975), 71–93. Zbl0318.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 Zbl0832.05039
- [19] P. Turán, Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436–452. Zbl0026.26903
- [20] L. C. van der Merwe, Total Domination Critical Graphs, Ph.D. Dissertation, University of South Africa (1998). Zbl0918.05069