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

Abstract

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

How to cite

top

Teresa 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. [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. [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. [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. [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. [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. [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. [7] D. Hanson and P. Wang, A note on extremal total domination edge critical graphs. Util. Math. 63 (2003), 89–96. Zbl1035.05063
  8. [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. [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. [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. [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. [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. [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. [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. [15] W. Mantel, Wiskundige Opgaven 10 (1906), 60–61. 
  16. [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. [17] J. Plesník, Critical graphs of given diameter. Acta F.R.N Univ Comen Math 30 (1975), 71–93. Zbl0318.05115
  18. [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. [19] P. Turán, Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436–452. Zbl0026.26903
  20. [20] L. C. van der Merwe, Total Domination Critical Graphs, Ph.D. Dissertation, University of South Africa (1998). Zbl0918.05069

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.