On Murty-Simon Conjecture II

Tao Wang, Ping Wang, Qinglin Yu

Abstract

A graph is diameter two edge-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter two edge-critical graph on $n$ vertices is at most $\lfloor \frac{n^{2}}{4} \rfloor$ and the extremal graph is the complete bipartite graph $K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil}$. In the series papers [7-9], the Murty-Simon Conjecture stated by Haynes et al. is not the original conjecture, indeed, it is only for the diameter two edge-critical graphs of even order. In this paper, we completely prove the Murty-Simon Conjecture for the graphs whose complements have vertex connectivity $\ell$, where $\ell = 1, 2, 3$; and for the graphs whose complements have an independent vertex cut of cardinality at least three.
BibTeX
@misc{wang2013murty,
  author = {Tao Wang and Ping Wang and Qinglin Yu},
  title = {{On Murty-Simon Conjecture II}},
  year = {2013},
  eprint = {1301.0460},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1301.0460},
}

Loading related content...

Figure