Counting k-cycles in 5-connected planar triangulations

2025/07/24 by Agrahari, Gyaneshwar, Liu, Xiaonan, Wang, Zhiyu
#05C10 #05C30 #05C38 #05C40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.18090

Abstract

We show that every n-vertex 5-connected planar triangulation has at most 9n-50 many cycles of length 5 for all n≥ 20 and this upper bound is tight. We also show that for every k≥ 6, there exists some constant C(k) such that for sufficiently large n, every n-vertex 5-connected planar graph has at most C(k) ⋅ n^\lfloork/3\rfloor many cycles of length k. This upper bound is asymptotically tight for all k≥ 6.

Citations

• The maximum number of odd cycles in a planar graph
• Counting cycles in planar triangulations
• The maximum number of copies of an even cycle in a planar graph
• Homomorphism counts in robustly sparse graphs
• The maximum number of 10- and 12-cycles in a planar graph
• Counting Hamiltonian cycles in planar triangulations
• Hamiltonian cycles in 4-connected planar and projective planar triangulations with few 4-separators
• Counting paths, cycles and blow-ups in planar graphs
• Counting paths, cycles, and blow‐ups in planar graphs
• Number of Hamiltonian cycles in planar triangulations
• Generalized Planar Turán Numbers
• The maximum number of minimal codewords in an [n,k]-code
• The maximum number of minimal codewords in long codes
• On the number of cycles of length k in a maximal planar graph

Related

• Counting cycles in planar triangulations
• The maximum number of induced C₅'s in a planar graph
• Number of Hamiltonian cycles in planar triangulations
• Planar graphs with the maximum number of induced 4-cycles or 5-cycles
• Counting Hamiltonian cycles in planar triangulations