首页 | 本学科首页   官方微博 | 高级检索  
     


A maximum degree theorem for diameter-2-critical graphs
Authors:Teresa W. Haynes  Michael A. Henning  Lucas C. van der Merwe  Anders Yeo
Affiliation: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号