A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free

Teresa W. Haynes; Michael A. Henning; Anders Yeo

doi:10.1016/j.disopt.2011.04.003

A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free

Teresa W. Haynes, Michael A. Henning, Anders Yeo

Mathematics and Applied Mathematics

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

10 Citations (Scopus)

Abstract

A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most ⁿ²4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.

Original language	English
Pages (from-to)	495-501
Number of pages	7
Journal	Discrete Optimization
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/j.disopt.2011.04.003
Publication status	Published - Aug 2011

Keywords

Claw-free
Diameter critical
Total domination edge critical

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.disopt.2011.04.003

Cite this

@article{2a376efde71a4d4cbb70890c0db7f888,

title = "A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free",

abstract = "A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n24 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.",

keywords = "Claw-free, Diameter critical, Total domination edge critical",

author = "Haynes, {Teresa W.} and Henning, {Michael A.} and Anders Yeo",

year = "2011",

month = aug,

doi = "10.1016/j.disopt.2011.04.003",

language = "English",

volume = "8",

pages = "495--501",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2011/8

Y1 - 2011/8

N2 - A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n24 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.

AB - A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n24 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.

KW - Claw-free

KW - Diameter critical

KW - Total domination edge critical

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

U2 - 10.1016/j.disopt.2011.04.003

DO - 10.1016/j.disopt.2011.04.003

M3 - Article

AN - SCOPUS:79960107433

SN - 1572-5286

VL - 8

SP - 495

EP - 501

JO - Discrete Optimization

JF - Discrete Optimization

IS - 3

ER -

A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this