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.
Special classes of graphs
Complete graphs Every complete graph with an odd number n {\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. The original formulation of the Oberwolfach problem asks how to make a seating chart for n {\displaystyle n} people over ( n − 1 ) / 2 {\displaystyle (n-1)/2} dinners in a given set of circular tables of different sizes, such that each participant sits next to each other exactly once. Walecki's theorem corresponds to the case where there is one single table. Walecki's original construction places n − 1 {\displaystyle n-1} of the vertices into a regular polygon, and covers the complete graph in this subset of vertices with ( n − 1 ) / 2 {\displaystyle (n-1)/2} Hamiltonian paths that zigzag across the polygon, with each path rotated from each other path by a multiple of π / ( n − 1 ) {\displaystyle \pi /(n-1)} . The paths can then all be completed to Hamiltonian cycles by connecting their ends through the remaining vertex. Expanding a vertex of a 2 k {\displaystyle 2k} -regular graph into a clique of 2 k {\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. 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, Daniela Kühn and Deryk Osthus proved in 2012 that every sufficiently large regular tournament has a Hamiltonian decomposition.
Planar graphs
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.
Prisms
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. 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.
Symmetric graphs 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.
… excerpt ends here. Continue reading the full article.
