On a conjecture of Murty and Simon on diameter 2-critical graphs

Teresa W. Haynes; Michael A. Henning; Lucas C. Van Der Merwe; Anders Yeo

doi:10.1016/j.disc.2011.05.007

On a conjecture of Murty and Simon on diameter 2-critical graphs

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

11 Citations (Scopus)

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 of order n is at most n²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.

Original language	English
Pages (from-to)	1918-1924
Number of pages	7
Journal	Discrete Mathematics
Volume	311
Issue number	17
DOIs	https://doi.org/10.1016/j.disc.2011.05.007
Publication status	Published - 6 Sept 2011

Keywords

Diameter critical
Total domination edge critical

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2011.05.007

Cite this

@article{bea376e20eb643dc9be9005a1dc75609,

title = "On a conjecture of Murty and Simon on diameter 2-critical graphs",

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 of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.",

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

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

year = "2011",

month = sep,

day = "6",

doi = "10.1016/j.disc.2011.05.007",

language = "English",

volume = "311",

pages = "1918--1924",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "17",

}

TY - JOUR

T1 - On a conjecture of Murty and Simon on diameter 2-critical graphs

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Van Der Merwe, Lucas C.

AU - Yeo, Anders

PY - 2011/9/6

Y1 - 2011/9/6

N2 - 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 of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.

AB - 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 of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.

KW - Diameter critical

KW - Total domination edge critical

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

U2 - 10.1016/j.disc.2011.05.007

DO - 10.1016/j.disc.2011.05.007

M3 - Article

AN - SCOPUS:79957949274

SN - 0012-365X

VL - 311

SP - 1918

EP - 1924

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 17

ER -

On a conjecture of Murty and Simon on diameter 2-critical graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this