Counting cycles in planar triangulations

2022/10/03 by On‐Hei Solomon Lo, Lo, On-Hei Solomon, Carol T. Zamfirescu +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2210.01190

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

Abstract

We investigate the minimum number of cycles of specified lengths in planar n-vertex triangulations G. It is proven that this number is Ω(n) for any cycle length at most 3 + max \ \rm rad(G^*), \lceil ((n-3)/(2))^log₃2 \rceil \, where \rm rad(G^*) denotes the radius of the triangulation's dual, which is at least logarithmic but can be linear in the order of the triangulation. We also show that there exist planar hamiltonian n-vertex triangulations containing O(n) many k-cycles for any k ∈ \ \lceil n - √[5]n \rceil, …, n \. Furthermore, we prove that planar 4-connected n-vertex triangulations contain Ω(n) many k-cycles for every k ∈ \ 3, …, n \, and that, under certain additional conditions, they contain Ω(n²) k-cycles for many values of k, including n.

Cited by

• Counting k-cycles in 5-connected planar triangulations

Related

• Counting k-cycles in 5-connected planar triangulations
• Number of Hamiltonian cycles in planar triangulations
• Counting Hamiltonian cycles in planar triangulations
• Hamiltonian cycles in 4-connected planar and projective planar triangulations with few 4-separators
• Counting Triangulations of Planar Point Sets