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

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)\le \lfloor \frac{n^2}{4}\rfloor$, with equality if and only if $G\cong K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{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)\le \frac{n^2}{6}+o(n^2)$ for diameter-3-critical graphs $G$, and $e(G)\le \frac{3n^2}{k}$ for diameter-$k$-critical graphs $G$ with $k\ge 4$. In this paper, we improve the bound for diameter-$k$-critical graphs to $\frac{n^2}{2k}+o(n^2)$.