"A Characterization of Diameter-2-Critical Graphs Whose Complements Are" by Teresa W. Haynes and Michael A. Henning
 

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.

Plum Print visual indicator of research metrics
PlumX Metrics
  • Citations
    • Citation Indexes: 5
  • Usage
    • Abstract Views: 8
  • Captures
    • Readers: 6
see details

Share

COinS