Large cycles in essentially 4-connected graphs

2020/03/21 by Michael C. Wigal, Xingxing Yu, Wigal, Michael +1
Computer Science · Mathematics · #05C38 #05C40 #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2003.09750

openalex publication_date 2020/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but there are 3-connected n-vertex planar graphs whose longest cycles have length Θ(n^log₃2). On the other hand, Jackson and Wormald in 1992 proved that an essentially 4-connected n-vertex planar graph contains a cycle of length at least (2n+4)/5, which was recently improved to 5(n+2)/8 by Fabrici \it et al. In this paper, we improve this bound to \lceil (2n+6)/3\rceil for n≥ 6, which is best possible, by proving a quantitative version of a result of Thomassen on Tutte paths.

Related

• Long cycles and spectral radii in planar graphs
• On the Circumference of Essentially 4-connected Planar Graphs
• Cycles of many lengths in Hamiltonian graphs
• On Tutte cycles containing three prescribed edges
• Regular graphs with few longest cycles