On diameter 2-critical graphs (Q1096642)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On diameter 2-critical graphs |
scientific article |
Statements
On diameter 2-critical graphs (English)
0 references
1987
0 references
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.]
0 references
size
0 references
number of edges
0 references
bound
0 references
graph
0 references
diameter 2-critical
0 references