Hamiltonian decomposition

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

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

One kind of analogue of a complete graph, in the case of directed graphs, is a tournament. 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]

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

The prism over a graph is its Cartesian product with the two-vertex complete graph. For instance, the prism over a cycle graph is the graph of a geometric prism. The 4-regular graphs obtained as prisms over 3-regular graphs have been particularly studied with respect to Hamiltonian decomposition. When the underlying 3-regular graph is 3-vertex-connected, the resulting 4-regular prism always has a Hamiltonian cycle and, in all examples that have been tested, a Hamiltonian decomposition. Based on this observation, Alspach and Rosenfeld conjectured in 1986 that all prisms over 3-regular 3-vertex-connected graphs have a Hamiltonian decomposition. As of 2015, the conjecture remains unsolved.[7][8]

Many classes of 3-regular 3-vertex-connected graphs are known to have prisms with Hamiltonian decompositions. In particular this occurs when the 3-regular graph is planar and bipartite, when it is a Halin graph, when it is itself a prism or Möbius ladder, or when it is a generalized Petersen graph of order divisible by four.[8][9]

There are infinitely many vertex-transitive graphs (graphs in which every vertex is symmetric to every other vertex) that do not have a Hamiltonian decomposition. In particular this applies to the Cayley graphs whose vertices describe the elements of a group and whose elements describe multiplication by generators of the group. Infinitely many 6-regular Cayley graphs have no Hamiltonian decomposition, and there exist Cayley graphs of arbitrarily large even degree with no 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.[3]