Improved bound on the number of edges of diameter-k-critical graphs

2024/09/26 by Wang, Xiaolin, Zhang, Yanbo, Zhu, Xiutao
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2409.17491

Abstract

A graph is diameter-k-critical if its diameter equals k and the deletion of any edge increases its diameter. The Murty-Simon Conjecture states that for any diameter-2-critical graph G of order n, e(G) ≤ \lfloor (n²)/(4)\rfloor, with equality if and only if G ≅ K_{\lfloor (n)/(2)\rfloor,\lceil (n)/(2)\rceil}. Füredi (JGT,1992) proved that this conjecture is true for sufficiently large n. Over two decades later, Loh and Ma (JCT-B, 2016) proved that e(G) ≤ (n²)/(6)+o(n²) for diameter-3-critical graphs G, and e(G) ≤ (3n²)/(k) for diameter-k-critical graphs G with k ≥ 4. In this paper, we improve the bound for diameter-k-critical graphs to (n²)/(2k)+o(n²).

Related

• Improving the Bounds On Murty_Simon Conjecture
• On Murty-Simon Conjecture
• Diameter critical graphs
• On Murty-Simon Conjecture II
• Strengthening the Murty-Simon conjecture on diameter 2 critical graphs