Progress on the Murty–Simon Conjecture on diameter-2 critical graphs: a survey

Teresa W. Haynes, Michael A. Henning, Lucas C. van der Merwe, Anders Yeo

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


A graph $$G$$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⌉. We survey the progress made to date on this conjecture, concentrating mainly on recent results developed from associating the conjecture to an equivalent one involving total domination.

Original languageEnglish
Pages (from-to)579-595
Number of pages17
JournalJournal of Combinatorial Optimization
Issue number3
Publication statusPublished - 1 Oct 2015


  • Diameter-2-critical
  • Total domination
  • Total domination edge-critical

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Progress on the Murty–Simon Conjecture on diameter-2 critical graphs: a survey'. Together they form a unique fingerprint.

Cite this