Improving the Bounds On Murty_Simon Conjecture

Abstract

A graph is said to be diameter-$k$-critical if its diameter is $k$ and removal of any of its edges increases its diameter. A beautiful conjecture by Murty and Simon, says that every diameter-2-critical graph of order $n$ has at most $\lfloor n^2/4\rfloor$ edges and equality holds only for $K_{\lceil n/2\rceil ,\lfloor n/2\rfloor }$. Haynes et al. proved that the conjecture is true for $\Delta \ge 0.7n$. They also proved that for $n>2000$, if $\Delta \ge 0.6789n$ then the conjecture is true. We will improve this bound by showing that the conjecture is true for every $n$ if $\Delta \ge 0.676n$.