On Hamiltonian Cycles in Claw-Free Cubic Graphs

Abstract

We show that every claw-free cubic graph of order n at least 8 has at most 2⌊n4⌋{2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs.

Keywords

• hamiltonian cycle
• claw-free graph
• cubic graph
• 05c70