Hamiltonian decomposition

Walecki's Hamiltonian decomposition of the complete graph ${\displaystyle K_{9}}$

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.^[1]

The medial graph 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.^[2]

Complete graphs[]

Every complete graph with an odd number ${\displaystyle n}$ 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 ${\displaystyle n-1}$ of the vertices into a regular polygon, and covers the complete graph in this subset of vertices with ${\displaystyle (n-1)/2}$ Hamiltonian paths that zigzag across the polygon, with each path rotated from each other path by a multiple of ${\displaystyle \pi /(n-1)}$. The paths can then all be completed to Hamiltonian cycles by connecting their ends through the remaining vertex.^[3]

Expanding a vertex of a ${\displaystyle 2k}$-regular graph into a clique of ${\displaystyle 2k}$ 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.^[4]

The directed case of complete graphs is tournaments. Answering a conjecture by Paul Kelly from 1968,^[5] Daniela Kühn and Deryk Osthus proved in 2012 that every sufficiently large regular tournament has a Hamiltonian decomposition.^[6]

Number of decompositions[]

Every 4-regular undirected graph has an even number of Hamiltonian decompositions. More strongly, for every two edges ${\displaystyle e}$ and ${\displaystyle f}$ of a 4-regular graph, the number of Hamiltonian decompositions in which ${\displaystyle e}$ and ${\displaystyle f}$ belong to the same cycle is even. If a ${\displaystyle 2k}$-regular graph has a Hamiltonian decomposition, it has at least a triple factorial number of decompositions,

${\displaystyle (3k-2)\cdot (3k-5)\cdots 7\cdot 4\cdot 1.}$

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.^[7]

Computational complexity[]

Testing whether an arbitrary graph has a Hamiltonian decomposition is NP-complete, both in the directed and undirected cases.^[8] In particular, the question is NP-complete for regular graphs of a specified even degree; e.g., for 4-regular graphs.

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.^[9][10] 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.^[11]

See also[]

• Linear arboricity, a different kind of constrained partition into subgraphs of maximum degree two

References[]