Backtracking algorithms for constructing the Hamiltonian decomposition of a 4-regular multigraph

Alexander V. Korostil, Andrei V. Nikolaev

We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skel…