Constructive upper bounds for cycle-saturated graphs of minimum size (Q5896826)

Summary: A graph \(G\) is said to be \(C_l\)-saturated if \(G\) contains no cycle of length \(l\), but for any edge in the complement of \(G\) the graph \(G+e\) does contain a cycle of length \(l\). The minimum number of edges of a \(C_l\)-saturated graph was shown by \textit{C. A. Barefoot} et al. [Discrete Math. 150, 31--48 (1996; Zbl 0856.05058)] to be between \(n+c_1{n\over l}\) and \(n+c_2{n\over l}\) for some positive constants \(c_1\) and \(c_2\). This confirmed a conjecture of Bollobás. Here we improve the value of \(c_2\) for \(l \geq 8\).