## 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

### Keywords:

saturated graphs; minimum size

Zbl 0719.05040