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

MaRDI QIDQ5026982zbMATH OpenFDO

Authors Carsten Thomassen, Carol T. Zamfirescu

Publication date 8 February 2022

Full work available at URL https://arxiv.org/abs/2104.06347, http://ajc.maths.uq.edu.au/pdf/81/ajc_v81_p334.pdf

zbMATH Keywords

Hamiltonian cycles3-regular graphs4-regular graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3512156 (Why is no real title available?)
• scientific article; zbMATH DE number 3540826 (Why is no real title available?)
• scientific article; zbMATH DE number 3577225 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• 4-connected polyhedra have at least a linear number of Hamiltonian cycles
• Graph theory with applications
• Graphs with few Hamiltonian cycles
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Independent dominating sets and a second hamiltonian cycle in regular graphs
• Independent dominating sets and hamiltonian cycles
• On Hamiltonian Circuits
• On the minimum number of Hamiltonian cycles in regular graphs
• On the number of Hamiltonian cycles in bipartite graphs
• Polytopes, graphs, and complexes
• Regular n-valent n-connected non-Hamiltonian non n-edge-colourable graphs

Cited in

(12)

• scientific article; zbMATH DE number 409961 (Why is no real title available?)
• From one to many rainbow Hamiltonian cycles
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• Regular graphs with few longest 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
• scientific article; zbMATH DE number 3877231 (Why is no real title available?)
• On the number of Hamilton cycles in bounded degree graphs

Describes a project that uses

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)