A characterization of the non-trivial diameter two graphs of minimum size

Michael A. Henning; Justin Southey

doi:10.1016/j.dam.2015.02.009

A characterization of the non-trivial diameter two graphs of minimum size

Michael A. Henning, Justin Southey

Mathematics and Applied Mathematics

University of Johannesburg

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

5 Citations (Scopus)

Abstract

Let G be a graph with diameter two, order n and size m, such that no vertex is adjacent to every other vertex. A classical result due to Erdos and Rényi (1962) states that m≥2n-5. We characterize the graphs that achieve equality in the Erdos-Rényi bound.

Original language	English
Pages (from-to)	91-95
Number of pages	5
Journal	Discrete Applied Mathematics
Volume	187
DOIs	https://doi.org/10.1016/j.dam.2015.02.009
Publication status	Published - 31 May 2015

Keywords

Bounds
Diameter two graphs
Size

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2015.02.009

Cite this

@article{cb782d6d3e62495493969c78a853c7de,

title = "A characterization of the non-trivial diameter two graphs of minimum size",

abstract = "Let G be a graph with diameter two, order n and size m, such that no vertex is adjacent to every other vertex. A classical result due to Erdos and R{\'e}nyi (1962) states that m≥2n-5. We characterize the graphs that achieve equality in the Erdos-R{\'e}nyi bound.",

keywords = "Bounds, Diameter two graphs, Size",

author = "Henning, {Michael A.} and Justin Southey",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = may,

day = "31",

doi = "10.1016/j.dam.2015.02.009",

language = "English",

volume = "187",

pages = "91--95",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A characterization of the non-trivial diameter two graphs of minimum size

AU - Henning, Michael A.

AU - Southey, Justin

PY - 2015/5/31

Y1 - 2015/5/31

N2 - Let G be a graph with diameter two, order n and size m, such that no vertex is adjacent to every other vertex. A classical result due to Erdos and Rényi (1962) states that m≥2n-5. We characterize the graphs that achieve equality in the Erdos-Rényi bound.

AB - Let G be a graph with diameter two, order n and size m, such that no vertex is adjacent to every other vertex. A classical result due to Erdos and Rényi (1962) states that m≥2n-5. We characterize the graphs that achieve equality in the Erdos-Rényi bound.

KW - Bounds

KW - Diameter two graphs

KW - Size

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

U2 - 10.1016/j.dam.2015.02.009

DO - 10.1016/j.dam.2015.02.009

M3 - Article

AN - SCOPUS:84928209745

SN - 0166-218X

VL - 187

SP - 91

EP - 95

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A characterization of the non-trivial diameter two graphs of minimum size

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this