Maximal and Minimal Vertex-Critical Graphs of Diameter Two

Jing Huang; Anders Yeo

doi:10.1006/jctb.1998.1852

Maximal and Minimal Vertex-Critical Graphs of Diameter Two

Jing Huang, Anders Yeo

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

3 Citations (Scopus)

Abstract

A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at least 12ν²-2ν^3/2+c₁νedges, wherec₁is some constant. We show that such a graph contains at most 12ν²-(2/2)ν^3/2+c₂νedges, wherec₂is some constant. We also construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at most 12 (5ν-12) edges. We show that such a graph must contain at least 12 (5ν-29) edges.

Original language	English
Pages (from-to)	311-325
Number of pages	15
Journal	Journal of Combinatorial Theory. Series B
Volume	74
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1998.1852
Publication status	Published - Nov 1998
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1998.1852

Cite this

@article{af2005a7652f4bbf9106a18a6130d9f0,

title = "Maximal and Minimal Vertex-Critical Graphs of Diameter Two",

abstract = "A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at least 12ν2-2ν3/2+c1νedges, wherec1is some constant. We show that such a graph contains at most 12ν2-(2/2)ν3/2+c2νedges, wherec2is some constant. We also construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at most 12 (5ν-12) edges. We show that such a graph must contain at least 12 (5ν-29) edges.",

author = "Jing Huang and Anders Yeo",

year = "1998",

month = nov,

doi = "10.1006/jctb.1998.1852",

language = "English",

volume = "74",

pages = "311--325",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Maximal and Minimal Vertex-Critical Graphs of Diameter Two

AU - Huang, Jing

AU - Yeo, Anders

PY - 1998/11

Y1 - 1998/11

N2 - A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at least 12ν2-2ν3/2+c1νedges, wherec1is some constant. We show that such a graph contains at most 12ν2-(2/2)ν3/2+c2νedges, wherec2is some constant. We also construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at most 12 (5ν-12) edges. We show that such a graph must contain at least 12 (5ν-29) edges.

AB - A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at least 12ν2-2ν3/2+c1νedges, wherec1is some constant. We show that such a graph contains at most 12ν2-(2/2)ν3/2+c2νedges, wherec2is some constant. We also construct, for eachν≥5 exceptν=6, a vertex-critical graph of diameter two onνvertices with at most 12 (5ν-12) edges. We show that such a graph must contain at least 12 (5ν-29) edges.

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

U2 - 10.1006/jctb.1998.1852

DO - 10.1006/jctb.1998.1852

M3 - Article

AN - SCOPUS:0040679861

SN - 0095-8956

VL - 74

SP - 311

EP - 325

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

Maximal and Minimal Vertex-Critical Graphs of Diameter Two

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this