Constructive upper bounds for cycle-saturated graphs of minimum size
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\).
- Cycle-saturated graphs of minimum size
- \(C_{2k}\)-saturated graphs with no short odd cycles
- On the number of edges in a minimum \(C_6\)-saturated graph
- Minimum C_k-saturated graphs
- All minimum \(C_{5}\)-saturated graphs
- Minimum C5‐saturated graphs
- Saturation numbers for families of graph subdivisions
- Cycle-saturated graphs with minimum number of edges
- Saturation in the hypercube and bootstrap percolation
- MinimumK2, 3-Saturated Graphs
- Constructive upper bounds for cycle-saturated graphs of minimum size
- The game of \(\mathcal F\)-saturator
This page was built for publication: Constructive upper bounds for cycle-saturated graphs of minimum size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896826)
