4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles

zbMATH Open1490.05149arXiv2104.06347MaRDI QIDQ5026982FDOQ5026982

Authors: Carsten Thomassen, Carol T. Zamfirescu 

Publication date: 8 February 2022

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.

Full work available at URL: https://arxiv.org/abs/2104.06347

Recommendations

• Regular graphs with few longest cycles
• Finding and enumerating Hamilton cycles in 4-regular graphs
• On the number of Hamiltonian cycles in bipartite graphs
• Hamilton cycles in regular 3-connected graphs
• On the minimum number of Hamiltonian cycles in regular graphs

zbMATH Keywords

Hamiltonian cycles3-regular graphs4-regular graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Cites Work

• Graph theory with applications
• Title not available (Why is that?)
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Title not available (Why is that?)
• Independent dominating sets and hamiltonian cycles
• On Hamiltonian Circuits
• Polytopes, graphs, and complexes
• On the minimum number of Hamiltonian cycles in regular graphs
• Independent dominating sets and a second hamiltonian cycle in regular graphs
• Regular \(n\)-valent \(n\)-connected non-Hamiltonian non \(n\)-edge-colourable graphs
• On the number of Hamiltonian cycles in bipartite graphs
• Title not available (Why is that?)
• 4-connected polyhedra have at least a linear number of Hamiltonian cycles
• Graphs with few Hamiltonian cycles
• Title not available (Why is that?)

Cited In (12)

• Title not available (Why is that?)
• Regular graphs with few longest cycles
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• From one to many rainbow Hamiltonian cycles
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
• Improved asymptotic upper bounds for the minimum number of longest cycles in regular graphs
• Few Hamiltonian cycles in graphs with one or two vertex degrees
• Hamiltonian cycles and 1-factors in 5-regular graphs
• Title not available (Why is that?)
• On the number of Hamilton cycles in bounded degree graphs

Uses Software

• GenerateUHG

This page was built for publication: \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5026982)