A Characterization of Diameter-2-Critical Graphs With No Antihole of Length Four
Document Type
Article
Publication Date
6-1-2012
Description
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.
Citation Information
Haynes, Teresa W.; and Henning, Michael A.. 2012. A Characterization of Diameter-2-Critical Graphs With No Antihole of Length Four. Central European Journal of Mathematics. Vol.10(3). 1125-1132. https://doi.org/10.2478/s11533-012-0022-x ISSN: 1895-1074