×

On \(C_5\)-saturated graphs with minimum size. (English) Zbl 0897.05050

Summary: A graph is \(C_5\)-free if it does not contain a 5-cycle. A \(C_5\)-free graph is \(C_5\)-saturated if adding any edge creates a 5-cycle. Let \(\text{sat} (C_5,n)\) be the minimum number of edges of an \(n\)-node \(C_5\)-saturated graph. Zs. Tuza [Acta Univ. Carol., Math. Phys. 30, No. 2, 161-167 (1989; Zbl 0719.05040)] speculated that \(\text{sat} (C_5,n)= {3 \over 2} n+O(1)\). We find \(\text{sat} (C_5,n)\) for \(n\leq 13\) and show that \(\text{sat} (C_5,n) \leq \lceil 10(n-1)/7 \rceil\) for all \(n\neq 4\).

MSC:

05C35 Extremal problems in graph theory

Citations:

Zbl 0719.05040
PDF BibTeX XML Cite