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

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 Barefoot et al. 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\).