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).

REFERENCES

Alspach, B.; Bermond, J.-C.; and Sotteau, D. "Decomposition Into Cycles. I. Hamilton Decompositions." In Proceedings of the NATO Advanced Research Workshop on Cycles and Rays: Basic Structures in Finite and Infinite Graphs held in Montreal, Quebec, May 3-9, 1987  (Ed. G. Hahn, G. Sabidussi, and R. E. Woodrow). Dordrecht, Holland: Kluwer, pp. 9-18, 1990.

Alspach, B. "The Wonderful Walecki Construction." Bull. Inst. Combin. Appl. 52, 7-20, 2008.

Alspach, B. "Three Hamilton Decomposition Problems." University of Western Australia. May 11, 2010.

 http://symomega.files.wordpress.com/2010/05/talk8.pdf.Alspach, B.; Bryant, D.; and Dyer, D. "Paley Graphs Have Hamilton Decompositions." Disc. Math. 312, 113-118, 2012.

Bosák, J. Decompositions of Graphs. New York: Springer, 1990.

Bryant, D. E. "Cycle Decompositions of Complete Graphs." In Surveys in Combinatorics 2007 (Eds. A. J. W. Hilton and J. M. Talbot). Cambridge, England: Cambridge University Press, 2007.

Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014.

 http://arxiv.org/abs/1408.5211.Dupuis, M. and Wagon, S. "Laceable Knights." To appear in Ars Math Contemp.Gould, R. J. "Advances on the Hamiltonian Problem-A Survey." Graphs Combin. 19, 7-52, 2003.

Kotzig, A. "Hamilton Graphs and Hamilton Circuits." In Theory of Graphs and Its Applications (Proc. Sympos. Smolenice). Praha: Nakl. CSAV, pp. 63-82, 1964.

Laskar, R. and Auerbach, B. "On Decomposition of -Partite Graphs into Edge-Disjoint Hamilton Circuits." Disc. Math. 14, 265-268, 1976.Lucas, É. Récréations Mathématiques, tome II. Paris, 1892.