Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size

Abstract

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$.