## Abstract

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n ^{2}/4⌋ and that the extremal graphs are the complete bipartite graphs K _{⌊n/2⌋,⌊n/2⌉}. Fan [Discrete Math. 67 (1987), 235-240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81-98] proved the conjecture for n > n _{0} where n _{0} is a tower of 2's of height about 10^{14}. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.

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

Pages (from-to) | 1882-1889 |

Number of pages | 8 |

Journal | Central European Journal of Mathematics |

Volume | 12 |

Issue number | 12 |

DOIs | |

Publication status | Published - Dec 2014 |

## Keywords

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

## ASJC Scopus subject areas

- General Mathematics