Saturation number for cycles of lengths congruent to 1 modulo 3

About 1 year old · traced to

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:k∈Z+}3\mathbb{Z}_++1=\{3k+1:k\in\mathbb{Z}_+\}. The conjecture. For every integer n≥1n\ge1,

sat⁡(n,C3Z++1)=⌈5n4−32⌉.\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.