4-regular 4-connected Hamiltonian graphs with few Hamiltonian cycles

2021/04/13 by Carsten Thomassen, Thomassen, Carsten, Carol T. Zamfirescu +1
Computer Science · Engineering · Mathematics · #05C30 (Secondary) #05C45 (Primary) 05C07 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2104.06347

openalex publication_date 2021/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that there exists an infinite family of 4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles. We do not know if there exists such a family of 5-regular 5-connected Hamiltonian graphs.

Related

• Regular graphs with few longest cycles
• On the Minimum Number of Hamiltonian Cycles in Regular Graphs
• Hamilton cycles in 5-connected line graphs
• Graphs with Many Hamiltonian Paths
• Few hamiltonian cycles in graphs with one or two vertex degrees