Saturation number for cycles of lengths congruent to 1 modulo 3

From papers

For an integer set II, let CI\mathcal{C}_I denote the family of cycles whose lengths belong to II, and let sat(n,CI)\operatorname{sat}(n,\mathcal{C}_I) be the minimum number of edges in an nn-vertex CI\mathcal{C}_I-saturated graph. Write 3Z++1={3k+1:kZ+}3\mathbb{Z}_++1=\{3k+1:k\in\mathbb{Z}_+\}. The conjecture. For every integer n1n\ge1,

sat(n,C3Z++1)=5n432.\operatorname{sat}(n, \mathcal{C}_{3\mathbb{Z}_++1})=\left\lceil\frac{5n}{4}-\frac{3}{2}\right\rceil.

The paper proves an analogous exact formula for C2Z++2\mathcal{C}_{2\mathbb{Z}_++2} but explicitly presents this assertion as an unresolved conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yue Ma, “Minimum saturated graphs without 4-cycles and 5-cycles”, arXiv:2503.16839 (2025).

Solutions 0

No solutions have been posted yet.