Hamiltonian decomposition

In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

A directed graph with such a decomposition must be strongly connected and all vertices must have the same in-degree and out-degree as each other, but this degree does not need to be even.

This result, which is a special case of the Oberwolfach problem of decomposing complete graphs into isomorphic 2-factors, was attributed to Walecki by Édouard Lucas in 1892.

The paths can then all be completed to Hamiltonian cycles by connecting their ends through the remaining vertex.

vertices, one for each endpoint of an edge at the replaced vertex, cannot change whether the graph has a Hamiltonian decomposition.

The reverse of this expansion process, collapsing a clique to a single vertex, will transform any Hamiltonian decomposition in the larger graph into a Hamiltonian decomposition in the original graph.

Conversely, Walecki's construction can be applied to the clique to expand any Hamiltonian decomposition of the smaller graph into a Hamiltonian decomposition of the expanded graph.

This is a graph in which every pair of distinct vertices is connected by a single directed edge, from one to the other; for instance, such a graph may describe the outcome of a round-robin tournament in sports, where each competitor in the tournament plays each other competitor, and edges are directed from the loser of each game to the winner.

Answering a conjecture by Paul Kelly from 1968,[4] Daniela Kühn and Deryk Osthus proved in 2012 that every sufficiently large regular tournament has a Hamiltonian decomposition.

[5] For 4-regular planar graphs, additional necessary conditions can be derived from Grinberg's theorem.

Based on this observation, Alspach and Rosenfeld conjectured in 1986 that all prisms over 3-regular 3-vertex-connected graphs have a Hamiltonian decomposition.

One way of constructing these graphs is to use repeated expansions by cliques, which preserve symmetry and cannot change the existence of a Hamiltonian decomposition.

[10] Testing whether an arbitrary graph has a Hamiltonian decomposition is NP-complete, both in the directed and undirected cases.

[12][13] As a consequence, Hamiltonian decomposition remains NP-complete for classes of graphs that include line graphs of hard instances of the Hamiltonian cycle problem.

On the other hand, this equivalence also implies that Hamiltonian decomposition is easy for 4-regular line graphs when their underlying cubic graphs have easy Hamiltonian cycle problems.