论文标题
3相连平面图的周期频谱中的紧密缝隙
Tight gaps in the cycle spectrum of 3-connected planar graphs
论文作者
论文摘要
对于任何积极的整数$ k $，定义$ f（k）$（分别为$ f_3（k）$）是最小整数$ \ ge k $，以使每个3个连接的平面图$ g $（分别为3个连接的立方平面图$ g $ g $ g $ \ ge g ge k $ ge k $ cy $ $ k $ in Interve $ k $ k（k） f_3（k）] $）。 默克（Merker）表明，任何$ k \ ge 2 $，$ f_3（k）\ le 2k + 9 $，以及$ f_3（k）\ ge 2k + 2 $，即使$ k \ ge 4 $。他推测，任何$ k \ ge 2 $ $ f_3（k）\ le 2k + 2 $。 Zamfirescu认为，这个猜想是对每个什至$ k \ ge 6 $的无限反例的家族的反驳，其图形在$ [k，2k + 2] $中没有周期长度，即$ f_3（k）\ ge 2k + 3 $，均为任何$ k \ ge 6 $ 6 $。但是，$ f_3（k）$的确切值仅以$ k \ le 4 $而闻名，并且它被打开以确定$ k \ ge 5 $的$ f_3（k）$。在本文中，我们改善了默克的上限，并为每$ k \ ge 5 $提供$ f_3（k）$的确切值。我们表明$ f_3（5）= 10 $，$ f_3（7）= 15 $，$ f_3（9）= 20 $，而$ f_3（k）= 2k + 3 $，对于任何$ k = 6、8 $或$ \ ge 10 $。 对于一般的三连接平面图，默克猜想存在一些正整数$ c $，因此对于任何正整数$ k $，$ f（k）\ le 2k + c $。我们对这个猜想给出了完全积极的答案。我们证明，对于任何$ k \ le 3 $，$ f（4）= 10 $，$ f（k）= 5 $，$ f（k）= 2k + 3 $对于任何$ k \ ge 5 $。
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$.
