A maximum degree theorem for diameter-2-critical graphs

• Autorzy: Teresa Haynes , Michael Henning , Lucas Merwe , Anders Yeo
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Diameter critical; Diameter-2-critical; Total domination critical

Kategorie tematyczne

• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2014
• Tom: 12
• Numer: 12
• Strony: 1882-1889

Daty

wydano

2014-12-01

online

2014-07-20

Twórcy

autor

Teresa Haynes

autor

Michael Henning

• University of Johannesburg

autor

Lucas Merwe

• University of Tennessee in Chattanooga

autor

Anders Yeo

Bibliografia

• [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.
• [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
• [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
• [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
• [7] D. Hanson and P. Wang, A note on extremal total domination edge critical graphs. Util. Math. 63 (2003), 89–96.
• [8] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York (1998).
• [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
• [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
• [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
• [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
• [13] T. W. Haynes, C. M. Mynhardt and L. C. van der Merwe, Total domination edge critical graphs. Util. Math. 54 (1998), 229–240.
• [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
• [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
• [17] J. Plesník, Critical graphs of given diameter. Acta F.R.N Univ Comen Math 30 (1975), 71–93.
• [18] B. Reed and N. Sbihi, Recognizing bull-free perfect graphs. Graphs Combin. 11 (1995), 171–178. http://dx.doi.org/10.1007/BF01929485
• [19] P. Turán, Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436–452.
• [20] L. C. van der Merwe, Total Domination Critical Graphs, Ph.D. Dissertation, University of South Africa (1998).

Identyfikatory

DOI

10.2478/s11533-014-0449-3