## 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 ⌊ ^{n2}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.

Original language | English |
---|---|

Pages (from-to) | 1979-1985 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 160 |

Issue number | 13-14 |

DOIs | |

Publication status | Published - Sept 2012 |

## Keywords

- Diameter critical
- Diameter-2-critical
- Total domination critical

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics