A -factor
of a graph is a spanning
-regular subgraph of the original graph. The special case of
a 1-factor is precisely a perfect matching. A
1-factorization of a graph is a partition of its edge set
into 1-factors. A pair of 1-factors whose union forms a Hamiltonian
cycle is said to be a set of perfect set of 1-factors, and a 1-factorization
is said to be perfect if all pairs of its 1-factors are perfect.
A regular graph of vertex degree
is then called a perfectly Hamiltonian graph if it admits a perfect 1-factorization.
In simpler terms, a graph is perfectly Hamiltonian if its edges can be colored in such a way that every two color classes (which represent pairs of 1-factors) form a Hamiltonian cycle.
The term was suggested by D. Knuth (pers. comm. to van Cleemput and Zamfirescu, Sep. 2019).
Every cubic graph containing exactly three hamiltonian cycles is perfectly hamiltonian. However, planar cubic perfectly hamiltonian graphs with more than three hamiltonian cycles also exist, and example of which is the dodecahedral graph (van Cleemput and Zamfirescu 2022).