1
$\begingroup$

Let $G$ be a graph.

Definition: $G$ is decomposable into two Hamiltonian cycles if the edge set $E(G)$ can be partitioned into two disjoint Hamiltonian cycles.

Obviously, if $G$ is decomposable into two Hamiltonian cycles, then $G$ must be a connected 4-regular graph, i.e. every vertex has degree 4.

But is it sufficient? "Every connected 4-regular graph is decomposable into two Hamiltonian cycles."

Some results said

"Every 4-regular Cayley graph on abelian group is decomposable into two Hamiltonian cycles."

"If $G$ is Eulerian, then it is decomposable into two 2-factors." (It is known that every connected graph of even degree is Eulerian, but a 2-factor may not be a Hamiltonian cycle)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.