## Abstract

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. 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_{⌊n/2⌋,⌈n/2⌉}. A graph is t-edge-critical, abbreviated 3_{t}EC, if its total domination number is 3 and the addition of any edge decreases the total domination number. It is known that proving the Murty–Simon Conjecture is equivalent to proving that the number of edges in a 3_{t}EC graph of order n is greater than ⌈n(n-2)/4⌉. We study a family F of 3_{t}EC graphs of diameter 2 for which every pair of nonadjacent vertices dominates the graph. We show that the graphs in F are precisely the bull-free 3_{t}EC graphs and that the number of edges in such graphs is at least ⌊(^{n2}-4)/4⌋, proving the conjecture for this family. We characterize the extremal graphs, and conjecture that this improved bound is in fact a lower bound for all 3_{t}EC graphs of diameter 2. Finally we slightly relax the requirement in the definition of F—instead of requiring that all pairs of nonadjacent vertices dominate to requiring that only most of these pairs dominate—and prove the Murty–Simon equivalent conjecture for these 3_{t}EC graphs.

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

Pages (from-to) | 1163-1176 |

Number of pages | 14 |

Journal | Graphs and Combinatorics |

Volume | 31 |

Issue number | 5 |

DOIs | |

Publication status | Published - 24 Sept 2015 |

## Keywords

- Bull-free
- Diameter critical
- Diameter-2-critical
- Domination
- Total domination edge critical

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics