Hamilton Decomposition

A Hamilton decomposition (also called a Hamiltonian decomposition; Bosák 1990, p. 123) of a Hamiltonian regular graph is a partition of its edge set into Hamiltonian cycles. The figure above illustrates the six distinct Hamilton decompositions of the pentatope graph .

The definition is sometimes extended to a decomposition into Hamiltonian cycles for a regular graph of even degree or into Hamiltonian cycles and a single perfect matching for a regular graph of odd degree (Alspach 2010), with a decomposition of the latter type being known as a quasi-Hamilton decomposition (Bosák 1990, p. 123).

For a cubic graph, a Hamilton decomposition is equivalent to a single Hamiltonian cycle. For a quartic graph, a Hamilton decomposition is equivalent to a Hamiltonian cycle , the removal of whose edges leaves a connected graph. When this connected graph exists, it gives the second of the pair of Hamiltonian cycles which together form the Hamilton decomposition . Iterating this procedure over all Hamiltonian cycles of a quartic graph generates each Hamilton decomposition twice, corresponding to the two different orderings and .

In the 1890s, Walecki showed that complete graphs admit a Hamilton decomposition for odd , and decompositions into Hamiltonian cycles plus a perfect matching for even (Lucas 1892, Bryant 2007, Alspach 2008).

In 1954, Ringel showed that the hypercube graph admits a Hamilton decompositions whenever is a power of 2 (Alspach 2010). Alspach et al. (1990) showed that every for admits a Hamilton decomposition.

Laskar and Auerbach (1976) showed that the complete bipartite graph has a (true) Hamilton decomposition whenever it is of even degree. In fact, has a true Hamilton decomposition iff and is even, and a quasi-Hamilton decomposition iff and is odd (Bosák 1990, p. 124). More generally, the complete -partite graph with has a Hamilton [quasi-Hamilton] decomposition iff and is even [odd] (Bosák 1990, p. 124).

Alspach et al. (2012) showed that Paley graphs admit Hamilton decompositions.

Kotzig (1964) showed that a cubic graph is Hamiltonian iff its line graph has a Hamilton decomposition (Bryant and Dean 2014).

It is not too difficult to find regular Hamiltonian non-vertex transitive graphs that are not Hamilton decomposable, as illustrated in the examples above.

It is more difficult to characterize regular Hamiltonian vertex-transitive graphs that are not Hamilton decomposable. S. Wagon (pers. comm., Feb. 2013; Dupuis and Wagon 2014) had conjectured that all connected vertex-transitive graphs are Hamilton decomposable with the following exceptions: , , , , , and . Here, denotes the Petersen graph, the Coxeter graph, denotes the triangle-replaced of , and the line graph of . Using the theorem of Kotzig (1964), Bryant and Dean (2014) added to this list. The conjecture can therefore be more simply stated as, "Every Hamiltonian vertex-transitive graph has a Hamilton decomposition except and ," which was verified up to nodes. (A slightly more general and precise statement of the conjecture can be made in terms of H-*-connected graphs.)

However, the conjecture was refuted by Bryant and Dean (2014), who showed that there are infinitely many connected vertex-transitive graphs that have no Hamilton decomposition, including infinitely many of vertex degree 6, and including Cayley graphs of arbitrarily large vertex degree. The counterexamples arise from a generalization of the triangle-replaced graph to -replaced -regular graphs, with the smallest counterexample given by the -replaced graph obtained from the multigraph obtained from the cubical graph by doubling its edges. In general, and are counterexamples, where denotes the multigraph obtained by taking copies of the edges of , , denotes the -vertex replacement operation on , and is the Möbius-Kantor graph (Bryant and Dean 2014).