Tight gaps in the cycle spectrum of 3-connected planar graphs

Abstract

For any positive integer $k$, define $f(k)$ (respectively, $f_3(k)$) to be the minimal integer $\ge k$ such that every 3-connected planar graph $G$ (respectively, 3-connected cubic planar graph $G$) of circumference $\ge k$ has a cycle whose length is in the interval $[k,f(k)]$ (respectively, $[k,f_3(k)]$). Merker showed that $f_3(k)\le 2k+9$ for any $k\ge 2$, and $f_3(k)\ge 2k+2$ for any even $k\ge 4$. He conjectured that $f_3(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_3(k)\ge 2k+3$ for any even $k\ge 6$. However, the exact value of $f_3(k)$ was only known for $k\le 4$, and it was left open to determine $f_3(k)$ for $k\ge 5$. In this paper we improve Merker's upper bound, and give the exact value of $f_3(k)$ for every $k\ge 5$. We show that $f_3(5)=10$, $f_3(7)=15$, $f_3(9)=20$, and $f_3(k)=2k+3$ for any $k=6,8$ or $\ge 10$. For general 3-connected planar graphs, Merker conjectured that there exists some positive integer $c$ such that $f(k)\le 2k+c$ for any positive integer $k$. We give a complete positive answer to this conjecture. We prove that $f(k)=5$ for any $k\le 3$, $f(4)=10$, and $f(k)=2k+3$ for any $k\ge 5$.