Name
Abstract | ||
|---|---|---|
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 @?n^2/4@? and that the extremal graphs are the complete bipartite graphs K"@?"n"/"2"@?"@?"n"/"2"@?. As a consequence of our characterization, we prove the Murty-Simon conjecture for graphs whose complements are diamond-free. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2012.03.037 | Discrete Applied Mathematics |
Keywords | Field | DocType |
order n,complete graph,extremal graph,diameter-2-critical graph,murty-simon conjecture,induced diamond subgraph,graph g,total domination,diamond-free graph,complete bipartite graph | Discrete mathematics,Combinatorics,Indifference graph,Forbidden graph characterization,Chordal graph,Cograph,Universal graph,1-planar graph,Pancyclic graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
160 | 13-14 | 0166-218X |
Citations | PageRank | References |
4 | 0.38 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Teresa W. Haynes | 1 | 774 | 94.22 |
| Michael A. Henning | 2 | 1865 | 246.94 |