2013/01/03 by Tao Wang, Ping Wang, Wang, Tao +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1301.0460
9 pages, submitted for publication on May 10, 2012
arxiv created 2013/01/03 · openalex publication_date 2013/01/03 · arxiv updated 2013/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \fracn24 \rfloor and the extremal graph is the complete bipartite graph K\lfloor (n)/(2) \rfloor, \lceil (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 ℓ, where ℓ = 1, 2, 3; and for the graphs whose complements have an independent vertex cut of cardinality at least three.