On a conjecture of Murty and Simon on diameter two critical graphs II

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

doi:10.1016/j.disc.2011.09.022

On a conjecture of Murty and Simon on diameter two critical graphs II

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 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 important association with total domination to prove the conjecture for the graphs whose complements have vertex connectivity k for k∈1,2,3.

Original language	English
Pages (from-to)	315-323
Number of pages	9
Journal	Discrete Mathematics
Volume	312
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2011.09.022
Publication status	Published - 28 Jan 2012

Keywords

Diameter 2-critical
Total domination edge critical
γ- critical

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2011.09.022

Cite this

@article{4108e8218e0a4cdf8dfcc1d5d4e3e572,

title = "On a conjecture of Murty and Simon on diameter two critical graphs II",

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 important association with total domination to prove the conjecture for the graphs whose complements have vertex connectivity k for k∈1,2,3.",

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

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

year = "2012",

month = jan,

day = "28",

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

language = "English",

volume = "312",

pages = "315--323",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

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

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2012/1/28

Y1 - 2012/1/28

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 important association with total domination to prove the conjecture for the graphs whose complements have vertex connectivity k for k∈1,2,3.

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 important association with total domination to prove the conjecture for the graphs whose complements have vertex connectivity k for k∈1,2,3.

KW - Diameter 2-critical

KW - Total domination edge critical

KW - γ- critical

UR - https://www.scopus.com/pages/publications/80955137580

U2 - 10.1016/j.disc.2011.09.022

DO - 10.1016/j.disc.2011.09.022

M3 - Article

AN - SCOPUS:80955137580

SN - 0012-365X

VL - 312

SP - 315

EP - 323

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

On a conjecture of Murty and Simon on diameter two critical graphs II

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this