|
|||||
|
|
A maximum degree theorem for diameter-2-critical graphs |
|
| Authors: | Teresa W Haynes Michael A Henning Lucas C van der Merwe Anders Yeo |
| Institution: | 1. Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN, 37614-0002, USA 2. Department of Mathematics, University of Johannesburg, Auckland Park, South Africa 3. Department of Mathematics, University of Tennessee in Chattanooga, Chattanooga, TN, 37403, USA 4. Engineering Systems and Design, Singapore University of Technology and Design, 20 Dover Drive, Singapore, 138682, Singapore |
| 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |