Improving the Bounds On Murty_Simon Conjecture

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\mathrm{/}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 $\mathrm{\Delta }\ge 0.7n$. They also proved that for $n>2000$, if $\Delta \geq 0.6789n$ then the conjecture is true. We will improve this bound by showing that the conjecture is true for every $n$ if $\mathrm{\Delta }\ge 0.676n$.