Size in maximal triangle-free graphs and minimal graphs of diameter 2
type: Item
instance of: scholarly article
title: Size in maximal triangle-free graphs and minimal graphs of diameter 2
zbMATH Open document ID: 0821.05031
DOI: 10.1016/0012-365X(94)00190-T
author: Curtiss Barefoot
author: Karen Casey
author: David C. Fisher
author: Kathryn Fraughnaugh
author: Frank Harary
published in: Discrete Mathematics
publication date: 1995-10-03T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 743999
zbMATH Keywords: triangle-free graphs
zbMATH Keywords: triangle
zbMATH Keywords: diameter
zbMATH Keywords: diameter-2 graph
reviewed by: Peter Brass
MaRDI profile type: Publication
cites work: On diameter critical graphs
cites work: On diameter 2-critical graphs
cites work: The maximum number of edges in a minimal graph of diameter 2
cites work: On the Möbius Ladders
cites work: Parallel concepts in graph theory
cites work: Q3220627
cites work: On some extremal graphs
cites work: Q5589881
cites work: On the theory of graphs
Recommended article: Q3487417
Recommended article: A characterization of the non-trivial diameter two graphs of minimum size
Recommended article: The size of maximally irregular graphs and maximally irregular triangle-free graphs
Recommended article: Q3216684
Recommended article: Q4838481
Recommended article: Maximal and minimal vertex-critical graphs of diameter two
Recommended article: Size of graphs and digraphs with given diameter and connectivity constraints
Recommended article: The maximum number of edges in a minimal graph of diameter 2
Recommended article: An Extremal Problem of Graphs with Diameter 2
Recommended article: Q5577693
description: scientific article; zbMATH DE number 743999