A characterization of diameter-2-critical graphs whose complements are diamond-free

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. The complete graph on four vertices minus one edge is called a diamond, and a diamond-free graph has no induced diamond subgraph. In this paper we use an association with total domination to characterize the diameter-2-critical graphs whose complements are diamond-free. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph G of order n is at most ⌊ ⁿ²4⌋ and that the extremal graphs are the complete bipartite graphs K⌊ _n2⌋n2⌉. As a consequence of our characterization, we prove the Murty-Simon conjecture for graphs whose complements are diamond-free.