Hamiltonian decomposition

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.

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

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]

Special classes of graphs

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

Planar graphs

 

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]

Prisms

Unsolved problem in mathematics:

Does every prism over a 3-connected 3-regular graph have a Hamiltonian decomposition?

(more unsolved problems in mathematics)

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^[update], 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]

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

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

Computational complexity

Testing whether an arbitrary graph has a Hamiltonian decomposition is NP-complete, both in the directed and undirected cases.^[11] 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.^[12][13] 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.^[14]

See also

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

References

1. Bermond, J.-C. (1978), "Hamiltonian decompositions of graphs, directed graphs and hypergraphs", Annals of Discrete Mathematics, 3: 21–28, doi:10.1016/S0167-5060(08)70494-1, ISBN 9780720408430, MR 0505807
2. Alspach, Brian (2008), "The wonderful Walecki construction", Bulletin of the Institute of Combinatorics and Its Applications, 52: 7–20, MR 2394738
3. Bryant, Darryn; Dean, Matthew (2015), "Vertex-transitive graphs that have no Hamilton decomposition", Journal of Combinatorial Theory, Series B, 114: 237–246, doi:10.1016/j.jctb.2015.05.007, MR 3354297
4. Moon, John W. (1968), Topics on Tournaments, New York, Montreal, London: Holt, Rinehart and Winston, Exercise 9, page 9, MR 0256919
5. Kühn, Daniela; Osthus, Deryk (2013), "Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments", Advances in Mathematics, 237: 62–146, arXiv:1202.6219, doi:10.1016/j.aim.2013.01.005, MR 3028574
6. Bondy, J. A.; Häggkvist, R. (1981), "Edge-disjoint Hamilton cycles in 4-regular planar graphs", Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007/BF02190157, MR 0623315
7. Alspach, Brian; Rosenfeld, Moshe (1986), "On Hamilton decompositions of prisms over simple 3-polytopes", Graphs and Combinatorics, 2 (1): 1–8, doi:10.1007/BF01788070, MR 1117125
8. Rosenfeld, Moshe; Xiang, Ziqing (2014), "Hamiltonian decomposition of prisms over cubic graphs", Discrete Mathematics & Theoretical Computer Science, 16 (2): 111–124, doi:10.46298/dmtcs.2079, MR 3349112
9. Čada, Roman; Kaiser, Tomá; Rosenfeld, Moshe; Ryjáček, Zdeněk (2004), "Hamiltonian decompositions of prisms over cubic graphs", Discrete Mathematics, 286 (1–2): 45–56, doi:10.1016/j.disc.2003.11.044, MR 2084278
10. Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, MR 0499124
11. Péroche, B. (1984), "NP-completeness of some problems of partitioning and covering in graphs", Discrete Applied Mathematics, 8 (2): 195–208, doi:10.1016/0166-218X(84)90101-X, MR 0743024
12. Kotzig, Anton (1957), "Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades", Časopis Pro Pěstování Matematiky, 82: 76–92, MR 0090815
13. Martin, Pierre (1976), "Cycles hamiltoniens dans les graphes 4-réguliers 4-connexes", Aequationes Mathematicae, 14 (1/2): 37–40, doi:10.1007/BF01836203, MR 0414442
14. Kim, Jeong Han; Wormald, Nicholas C. (2001), "Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs", Journal of Combinatorial Theory, Series B, 81 (1): 20–44, doi:10.1006/jctb.2000.1991, MR 1809424