In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs; in the undirected case, a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.
Necessary conditions
For a Hamiltonian decomposition to exist in an undirected graph, the graph must be connected and regular of even degree. 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. of the Herschel graph is a 4-regular planar graph with no Hamiltonian decomposition. The shaded regions correspond to the vertices of the underlying Herschel graph. For 4-regular planar graphs, additional necessary conditions can be derived from Grinberg's theorem. An example of a 4-regular planar graph that does not meet these conditions, and does not have a Hamiltonian decomposition, is given by the medial graph of the Herschel graph.
Complete graphs
Every complete graph with an odd number of vertices has a Hamiltonian decomposition. 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. Walecki's construction places of the vertices into a regular polygon, and covers the complete graph in this subset of vertices with Hamiltonian paths that zigzag across the polygon, with each path rotated from each other path by a multiple of. The paths can then all be completed to Hamiltonian cycles by connecting their ends through the remaining vertex. Expanding a vertex of a -regular graph into a clique of 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 expansion process can be used to produce arbitrarily large vertex-transitive graphs and Cayley graphs of even degree that do not have Hamiltonian decompositions. The directed case of complete graphs are tournaments. Answering a conjecture by Paul Kelly from 1968, Daniela Kühn and Deryk Osthus proved in 2012 that every sufficiently large regular tournament has a Hamiltonian decomposition.
Number of decompositions
Every 4-regular undirected graph has an even number of Hamiltonian decompositions. More strongly, for every two edges and of a 4-regular graph, the number of Hamiltonian decompositions in which and belong to the same cycle is even. If a -regular graph has a Hamiltonian decomposition, it has at least a triple factorial number of decompositions, For instance, 4-regular graphs that have a Hamiltonian decomposition have at least four of them; 6-regular graphs that have a Hamiltonian decomposition have at least 28, etc. It follows that the only graphs whose Hamiltonian decompositions are unique are the cycle graphs.
Computational complexity
Testing whether an arbitrary graph has a Hamiltonian decomposition is NP-complete, both in the directed and undirected cases. The line graphs of cubic graphs are 4-regular, and have a Hamiltonian decomposition if and only if the underlying cubic graph has a Hamiltonian cycle. As a consequence, Hamiltonian decomposition remains NP-complete for classes of graphs that include line graphs of hard instances of the Hamiltonian cycle problem. For instance, Hamiltonian decomposition is NP-complete for the 4-regular planar graphs, because they include the line graphs of cubic planar graphs. 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. Random regular graphs of even degree almost surely have a Hamiltonian decomposition, and more strongly there is a randomized polynomial time algorithm which, when given as input a random regular graph of even degree, almost surely finds a Hamiltonian decomposition in it.
