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

doi:10.1007/s10878-013-9651-7

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

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

Abstract

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 ⌊ⁿ²/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 language	English
Pages (from-to)	579-595
Number of pages	17
Journal	Journal of Combinatorial Optimization
Volume	30
Issue number	3
DOIs	https://doi.org/10.1007/s10878-013-9651-7
Publication status	Published - 1 Oct 2015

Keywords

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

Access to Document

10.1007/s10878-013-9651-7

Cite this

@article{26c7b05708644542bdd5357edd7d1d25,

title = "Progress on the Murty–Simon Conjecture on diameter-2 critical graphs: a survey",

abstract = "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.",

keywords = "Diameter-2-critical, Total domination, Total domination edge-critical",

author = "Haynes, {Teresa W.} and Henning, {Michael A.} and {van der Merwe}, {Lucas C.} and Anders Yeo",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Science+Business Media New York.",

year = "2015",

month = oct,

day = "1",

doi = "10.1007/s10878-013-9651-7",

language = "English",

volume = "30",

pages = "579--595",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Progress on the Murty–Simon Conjecture on diameter-2 critical graphs

T2 - a survey

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - van der Merwe, Lucas C.

AU - Yeo, Anders

PY - 2015/10/1

Y1 - 2015/10/1

N2 - 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.

AB - 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.

KW - Diameter-2-critical

KW - Total domination

KW - Total domination edge-critical

UR - http://www.scopus.com/inward/record.url?scp=84940718088&partnerID=8YFLogxK

U2 - 10.1007/s10878-013-9651-7

DO - 10.1007/s10878-013-9651-7

M3 - Article

AN - SCOPUS:84940718088

SN - 1382-6905

VL - 30

SP - 579

EP - 595

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this