graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

s. Hamiltonian decompositions have been studied both for

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

s 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 In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are thems ...

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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

with an odd number

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 __NOTOC__ François Édouard Anatole Lucas (; 4 April 1842 – 3 October 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him. Biography Luc ...

in 1892. Walecki's construction places

n-1

of the vertices into a regular polygon, and covers the complete graph in this subset of vertices with

(n-1)/2

Hamiltonian paths that zigzag across the polygon, with each path rotated from each other path by a multiple of

\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

2k

-regular graph into a

clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

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 A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concen ...

. 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 A round-robin tournament or all-play-all tournament is a competition format in which each contestant meets every other participant, usually in turn.''Webster's Third New International Dictionary of the English Language, Unabridged'' (1971, G. & ...

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 graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s, additional necessary conditions can be derived from

Grinberg's theorem In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely use ...

. 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 In graph theory, a branch of mathematics, the Herschel graph is a bipartite graph, bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph (the graph of a convex polyhedron), and is the smallest polyhedral graph that d ...

Prisms

The ''prism'' over a graph is its

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

with the two-vertex complete graph. For instance, the prism over a

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

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 In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree (graph theory), tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in ...

, when it is itself a prism or

Möbius ladder In graph theory, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of (the util ...

, or when it is a generalized Petersen graph of order divisible by four.

Symmetric graphs

There are infinitely many

vertex-transitive graph In the mathematics, mathematical field of graph theory, an Graph automorphism, automorphism is a permutation of the Vertex (graph theory), vertices such that edges are mapped to edges and non-edges are mapped to non-edges. A graph is a vertex-tr ...

s (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 graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...

s whose vertices describe the elements of a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...

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.

Uniform Hypergraphs

Decomposition problems for hypergraphs are in general much harder than for graphs. Unlike graphs, hypergraphs admit multiple non-equivalent notions of cycles (see Hypergraph cycles). The simplest of these notions is the Berge-cycle. In 2014, Kühn and Osthus showed that the complete

k

-uniform hypergraph

K_n^

admits a decomposition into Hamilton Berge-cycles whenever

n

divides

. However, for the most commonly used notion of cycle in hypergraph —the tight cycle— it remains an open problem whether the complete

k

-uniform hypergraph

K_n^

admits a Hamiltonian decomposition. Baranyai's theorem addresses a similar problem, by finding a decomposition of the complete

k

-uniform hypergraph into perfect matchings.

Number of decompositions

Every 4-regular undirected graph has an even number of Hamiltonian decompositions. More strongly, for every two edges

e

and

f

of a 4-regular graph, the number of Hamiltonian decompositions in which

e

and

f

belong to the same cycle is even. If a

2k

-regular graph has a Hamiltonian decomposition, it has at least a triple factorial number of decompositions, :

(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

Computational complexity

Testing whether an arbitrary graph has a Hamiltonian decomposition is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

, both in the directed and undirected cases. In particular, the question is NP-complete for regular graphs of a specified even degree; e.g., for 4-regular graphs. The

line graph In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...

s of

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bip ...

s are 4-regular and have a Hamiltonian decomposition if and only if the underlying cubic graph has a Hamiltonian cycle. 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 graph A random ''r''-regular graph is a graph selected from \mathcal_, which denotes the probability space of all ''r''-regular graphs on n vertices, where 3 \le r 0 is a positive constant, and d is the least integer satisfying (r-1)^ \ge (2 + \epsilon ...

s of even degree

almost surely In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (with respect to the probability measure). In other words, the set of outcomes on which the event does not occur ha ...

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.

References

{{reflist, refs= {{citation , last = Alspach , first = Brian , authorlink = Brian Alspach , journal = Bulletin of the Institute of Combinatorics and Its Applications , mr = 2394738 , pages = 7–20 , title = The wonderful Walecki construction , volume = 52 , year = 2008 {{citation , last1 = Alspach , first1 = Brian , author1-link = Brian Alspach , last2 = Rosenfeld , first2 = Moshe , doi = 10.1007/BF01788070 , issue = 1 , journal =

Graphs and Combinatorics ''Graphs and Combinatorics'' (ISSN 0911-0119, abbreviated ''Graphs Combin.'') is a peer-reviewed academic journal in graph theory, combinatorics, and discrete geometry published by Springer Japan. Its editor-in-chief is Katsuhiro Ota of Keio Univ ...

, mr = 1117125 , pages = 1–8 , title = On Hamilton decompositions of prisms over simple 3-polytopes , volume = 2 , year = 1986 {{citation , last = Bermond , first = J.-C. , doi = 10.1016/S0167-5060(08)70494-1 , journal = Annals of Discrete Mathematics , mr = 0505807 , pages
21–28
, title = Hamiltonian decompositions of graphs, directed graphs and hypergraphs , volume = 3 , year = 1978 , isbn = 9780720408430 , url = https://archive.org/details/advancesingrapht0000camb/page/21 {{citation , last1 = Bryant , first1 = Darryn , last2 = Dean , first2 = Matthew , doi = 10.1016/j.jctb.2015.05.007 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...

, series=Series B , mr = 3354297 , pages = 237–246 , title = Vertex-transitive graphs that have no Hamilton decomposition , volume = 114 , year = 2015, doi-access = free , arxiv = 1408.5211 {{citation , last1 = Bondy , first1 = J. A. , author1-link = John Adrian Bondy , last2 = Häggkvist , first2 = R. , doi = 10.1007/BF02190157 , issue = 1 , journal = Aequationes Mathematicae , mr = 623315 , pages = 42–45 , title = Edge-disjoint Hamilton cycles in 4-regular planar graphs , volume = 22 , year = 1981 {{citation , last1 = Čada , first1 = Roman , last2 = Kaiser , first2 = Tomá , last3 = Rosenfeld , first3 = Moshe , last4 = Ryjáček , first4 = Zdeněk , doi = 10.1016/j.disc.2003.11.044 , issue = 1–2 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 2084278 , pages = 45–56 , title = Hamiltonian decompositions of prisms over cubic graphs , volume = 286 , year = 2004, doi-access = {{citation , last1 = Kim , first1 = Jeong Han , author1-link = Jeong Han Kim , last2 = Wormald , first2 = Nicholas C. , author2-link = Nick Wormald , doi = 10.1006/jctb.2000.1991 , issue = 1 , journal =

, series=Series B , mr = 1809424 , pages = 20–44 , title = Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs , volume = 81 , year = 2001, doi-access = free {{citation , last = Kotzig , first = Anton , authorlink = Anton Kotzig , journal = Časopis Pro Pěstování Matematiky , mr = 0090815 , pages = 76–92 , title = Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades , volume = 82 , year = 1957, doi = 10.21136/CPM.1957.117236 , doi-access = free {{citation , last1 = Kühn , first1 = Daniela , author1-link = Daniela Kühn , last2 = Osthus , first2 = Deryk , author2-link = Deryk Osthus , journal =

Advances in Mathematics ''Advances in Mathematics'' is a peer-reviewed scientific journal covering research on pure mathematics. It was established in 1961 by Gian-Carlo Rota. The journal publishes 18 issues each year, in three volumes. At the origin, the journal aimed ...

, mr = 3028574 , pages = 62–146 , title = Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments , doi = 10.1016/j.aim.2013.01.005 , doi-access=free , volume = 237 , year = 2013, arxiv = 1202.6219 {{citation , last = Martin , first = Pierre , doi = 10.1007/BF01836203 , issue = 1/2 , journal = Aequationes Mathematicae , mr = 0414442 , pages = 37–40 , title = Cycles hamiltoniens dans les graphes 4-réguliers 4-connexes , volume = 14 , year = 1976 {{citation , last = Moon , first = John W. , at = Exercise 9, page 9 , mr = 0256919 , publisher = Holt, Rinehart and Winston , location = New York, Montreal, London , title = Topics on Tournaments , url = https://www.gutenberg.org/ebooks/42833 , year = 1968 {{citation , last = Péroche , first = B. , doi = 10.1016/0166-218X(84)90101-X , issue = 2 , journal = Discrete Applied Mathematics , mr = 743024 , pages = 195–208 , title = NP-completeness of some problems of partitioning and covering in graphs , volume = 8 , year = 1984, doi-access = free {{citation , last1 = Rosenfeld , first1 = Moshe , last2 = Xiang , first2 = Ziqing , doi = 10.46298/dmtcs.2079 , issue = 2 , journal = Discrete Mathematics & Theoretical Computer Science , mr = 3349112 , pages = 111–124 , title = Hamiltonian decomposition of prisms over cubic graphs , volume = 16 , year = 2014, doi-access = free {{citation , last = Thomason , first = A. G. , contribution = Hamiltonian cycles and uniquely edge colourable graphs , mr = 499124 , pages = 259–268 , series = Annals of Discrete Mathematics , title = Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , volume = 3 , year = 1978 Graph theory objects NP-complete problems