Tight gaps in the cycle spectrum of 3-connected cubic planar graphs.
2020
For any positive integer $k$, define $f(k)$ to be the minimal integer $\ge k$ such that every 3-connected cubic planar graph $G$ of circumference $\ge k$ has a cycle whose length is in the interval $[k, f(k)]$. Merker showed that $f(k) \le 2k + 9$ for any $k \ge 2$, and $f(k) \ge 2k + 2$ for any even $k \ge 4$. He conjectured that $f(k) \le 2k + 2$ for any $k \ge 2$. This conjecture was disproved by Zamfirescu, who gave an infinite family of counterexamples for every even $k \ge 6$ whose graphs have no cycle length in $[k, 2k + 2]$, i.e. $f(k) \ge 2k + 3$ for any even $k \ge 6$. However, the exact value of $f(k)$ was only known for $k \le 4$, and it was left open to determine $f(k)$ for $k \ge 5$. In this note we give the exact value of $f(k)$ for every $k \ge 5$. We show that $f(5) = 10$, $f(7) = 15$, $f(9) = 20$, and $f(k) = 2k + 3$ for any $k = 6, 8$ or $k \ge 10$.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
2
References
0
Citations
NaN
KQI