Maximal and minimal vertex-critical graphs of diameter two
type: Item
instance of: scholarly article
title: Maximal and minimal vertex-critical graphs of diameter two
zbMATH Open document ID: 0904.05054
author: Jing Huang
author: A. Yeo
published in: Journal of Combinatorial Theory. Series B
publication date: 1998-09-10T00:00:00Z
review text: A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for each \(\nu\geq 5\) except \(\nu= 6\), a vertex-critical graph of diameter two on \(\nu\) vertices with at least \(\frac 12\nu^2- \sqrt{2}\nu^{\frac 32}+ c_1\nu\) edges, where \(c_1\) is some constant. We show that such a graph contains at most \(\frac 12\nu^2- \frac{\sqrt{2}}{2} \nu^{\frac 32}+ c_2\nu\) edges, where \(c_2\) is some constant. We also construct, for each \(\nu\geq 5\) except \(\nu=6\), a vertex-critical graph of diameter two on \(\nu\) vertices with at most \(\frac 12 (5\nu-12)\) edges. We show such a graph must contain at least \(\frac 12 (5\nu-29)\) edges.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1186388
zbMATH Keywords: diameter
zbMATH Keywords: critical graph
zbMATH Keywords: number of edges
MaRDI profile type: Publication
OpenAlex ID: W2144012227
cites work: The minimum number of edges in a vertex diameter-2-critical graph
cites work: Q3469118
cites work: Q5422499
cites work: On vertex critical graphs with prescribed diameter
cites work: Q4359591
cites work: Q3966172
cites work: Vertex-critical graphs of given diameter
cites work: Q4079637
cites work: The complexity of designing a network with minimum diameter
DOI: 10.1006/JCTB.1998.1852
description: scientific article; zbMATH DE number 1186388