A Characterization of Diameter-2-Critical Graphs Whose Complements Are Diamond-Free
Document Type
Article
Publication Date
9-1-2012
Description
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 ⌊ n24⌋ 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.
Citation Information
Haynes, Teresa W.; and Henning, Michael A.. 2012. A Characterization of Diameter-2-Critical Graphs Whose Complements Are Diamond-Free. Discrete Applied Mathematics. Vol.160(13-14). 1979-1985. https://doi.org/10.1016/j.dam.2012.03.037 ISSN: 0166-218X