On diameter 2-critical graphs
type: Item
instance of: scholarly article
title: On diameter 2-critical graphs
zbMATH Open document ID: 0634.05041
DOI: 10.1016/0012-365X(87)90174-9
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: A graph G is diameter 2-critical if \(diam(G)=2\) and \(diam(G-e)>2\) for any its edge e. The reviewer and Simon and Murty conjectured that if G has n vertices and m edges then \(m\leq n^ 2/4\). In this paper it is proved the conjecture for \(n\leq 24\) and also bound \(m<0.2532n^ 2\) for \(n\geq 25\). [Reviewer's remark: Recently Z. Füredi proved the conjecture for very big n.]
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4031732
zbMATH Keywords: size
zbMATH Keywords: number of edges
zbMATH Keywords: bound
zbMATH Keywords: graph
zbMATH Keywords: diameter 2-critical
author: Genghua Fan
MaRDI profile type: Publication
cites work: On diameter critical graphs
cites work: Q4079637
cites work: Q3686743
description: scientific article; zbMATH DE number 4031732