Size in maximal triangle-free graphs and minimal graphs of diameter 2 (Q1842148)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Size in maximal triangle-free graphs and minimal graphs of diameter 2 |
scientific article |
Statements
Size in maximal triangle-free graphs and minimal graphs of diameter 2 (English)
0 references
3 October 1995
0 references
The authors study triangle-free graphs which are maximal in the sense that the addition of any edge creates a triangle. They show that a maximal triangle-free graph with \(n\geq 5\) vertices is either a complete bipartite graph or has a number \(e\) of edges with \(2n- 5\leq e\leq \left\lfloor{1\over 4} (n- 1)^ 2\right\rfloor+ 1\), and construct an example for each of these possible edge-numbers. They also study graphs of diameter 2 which are minimal in the sense that the deletion of any edge increases the diameter. A triangle-free graph is minimal of diameter 2 if and only if it is maximal triangle-free. Using a result of Füredi that for \(n> n_ 0\) a nonbipartite minimal diameter-2 graph has at most \(\left\lfloor{1\over 4} (n- 1)^ 2\right\rfloor+ 1\) edges, they show that for \(n> n_ 0\) a non-bipartite \(n\)-vertex \(e\)-edge minimal diameter-2 graph exists if and only if \(2n- 5\leq e\leq \left\lfloor{1\over 4}(n- 1)^ 2\right\rfloor+ 1\). There is a 6-vertex 8-edge nonbipartite minimal diameter-2 graph, so \(n_ 0\geq 6\).
0 references
triangle-free graphs
0 references
triangle
0 references
diameter
0 references
diameter-2 graph
0 references