Circumference of essentially 4-connected planar triangulations

2021/06/02 by Fabrici, Igor, Harant, Jochen, Mohr, Samuel +1
#05C10 #05C38 #Mathematik #circumference #essentially 4-connected #long cycle #triangulation

paper · doi:10.15480/882.3580

Abstract

A 3-connected graph G is essentially 4-connected if, for any 3-cut S⊆V(G) of G, at most one component of G−S contains at least two vertices. We prove that every essentially 4-connected maximal planar graph G on n vertices contains a cycle of length at least 23(n+4); moreover, this bound is sharp.

Related

• On the Circumference of Essentially 4-connected Planar Graphs
• Large cycles in essentially 4-connected graphs
• Counting cycles in planar triangulations
• Disconnected cuts in 4-connected planar graphs
• Counting Hamiltonian cycles in planar triangulations