Name
Abstract | ||
|---|---|---|
For any positive integer k, define f(k) (respectively, f(3)(k)) to be the minimal integer >= k such that every 3-connected planar graph G (respectively, 3-connected cubic planar graph G) of circumference >= k has a cycle whose length is in the interval [k, f(k)] (respectively, [k, f(3)(k)]). Merker showed that f(3)(k) <= 2k + 9 for any k >= 2, and f(3)(k) >= 2k + 2 for any even k >= 4. He conjectured that f(3)(k) <= 2k + 2 for any k >= 2. This conjecture was disproved by Zamfirescu, who gave an infinite family of counterexamples for every even k >= 6 whose graphs have no cycle length in [k, 2k + 2], i.e., f(3)(k) >= 2k + 3 for any even k >= 6. However, the exact value of f(3)(k) was only known for k <= 4, and it is a natural problem to determine f(3)(k) for k >= 5. In this paper, we improve Merker's upper bound, and give the exact value of f(3)(k) for every k >= 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 >= 10. For general 3-connected planar graphs, Merker conjectured that there exists some positive integer c such that f(k) <= 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 <= 3, f(4) = 10, and f(k) = 2k + 3 for any k >= 5. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/20M1366770 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
cycle spectrum, 3-connected planar graphs, 3-connected cubic planar graphs | Journal | 35 |
Issue | ISSN | Citations |
3 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qing Cui | 1 | 75 | 13.89 |
| On-Hei Solomon Lo | 2 | 0 | 2.03 |