## Abstract

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no induced path on five vertices. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most ^{n2}/4 and that the extremal graphs are the complete bipartite graphs with partite sets whose cardinality differs by at most one. We use an association with total domination to prove that if G is a diameter-2-critical graph with no induced path ^{P5}, then G is triangle-free. As a consequence, we observe that the Murty-Simon Conjecture is true for ^{P5}-free, diameter-2-critical graphs by Turán's Theorem. Finally we characterize these graphs by characterizing their complements.

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

Pages (from-to) | 135-139 |

Number of pages | 5 |

Journal | Discrete Applied Mathematics |

Volume | 169 |

DOIs | |

Publication status | Published - 31 May 2014 |

## Keywords

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

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'A characterization of^{P 5}-free, diameter-2-critical graphs'. Together they form a unique fingerprint.