Maximal and Minimal Vertex-Critical Graphs of Diameter Two

Authors: Huang, J.1; Yeo, A.2

Source: Journal of Combinatorial Theory, Series B, Volume 74, Number 2, November 1998 , pp. 311-325(15)

Publisher: Academic Press

Buy & download fulltext article:

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.

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 ½2-2 3/2+c1 edges, where c1 is some constant. We show that such a graph contains at most ½2-(2/2) 3/2+c2 edges, where c2 is some constant. We also construct, for each 5 except =6, a vertex-critical graph of diameter two on vertices with at most ½ (5-12) edges. We show that such a graph must contain at least ½ (5-29) edges. Copyright 1998 Academic Press.

Document Type: Research Article

Affiliations: 1: Department of Mathematics and Statistics, University of Victoria, Victoria, British Columbia, V8W 3P4, Canada 2: Department of Mathematics and Computer Science, Odense University, Odense, DK-5230, Denmark

Publication date: November 1, 1998

Related content

Tools

Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page