TOPICS
Search

Perfectly Hamiltonian Graph


A k-factor of a graph is a spanning k-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 d 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).


See also

Hamiltonian Cycle, Perfect Matching

Explore with Wolfram|Alpha

References

van Cleemput, N. and Zamfirescu, C. T. "Hamiltonian Cycles and 1-Factors in 5-Regular Graphs." 24 Apr 2022. https://arxiv.org/abs/2008.03173.

Cite this as:

Weisstein, Eric W. "Perfectly Hamiltonian Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PerfectlyHamiltonianGraph.html

Subject classifications