On Murty-Simon Conjecture II

arXiv1301.0460MaRDI QIDQ6238468FDOQ6238468

Authors: Tao Wang, Ping Wang, Qinglin Roger Yu 

Publication date: 3 January 2013

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 $lfloorfrac{n}^{2}4floor$ and the extremal graph is the complete bipartite graph $K_{lfloorfracn2floor,lceilfracn2ceil}$. 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.

This page was built for publication: On Murty-Simon Conjecture II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6238468)