| Autor: |
Teresa W. Haynes, Michael A. Henning, Lucas C. van der Merwe, Anders Yeo |
| Rok vydání: |
2014 |
| Předmět: |
|
| Zdroj: |
Open Mathematics, Vol 12, Iss 12, Pp 1882-1889 (2014) |
| ISSN: |
2391-5455 |
| DOI: |
10.2478/s11533-014-0449-3 |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
