Saturation number for cycles of lengths congruent to 2 modulo a

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 aZ++2={ak+2:kZ+}a\mathbb{Z}_++2=\{ak+2:k\in\mathbb{Z}_+\}. The conjecture. For integers a2a\ge2 and na+1n\ge a+1,

sat(n,CaZ++2)=n+(a2)1.\operatorname{sat}(n, \mathcal{C}_{a\mathbb{Z}_++2})=n+\binom{a}{2}-1.

The preceding fact supplies the matching upper bound, but the source does not state a proof of the required lower bound; this exact formula is therefore left as a 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.