graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a branch of mathematics, a Hamiltonian decomposition of a given graph is a

partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...

of the edges of the graph into

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

s. Hamiltonian decompositions have been studied both for

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

s and for

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

s. 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 Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

. 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 an arbitrary directed graph form a partition into subgraphs that a ...

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 is c ...

with an odd number

n

of vertices has a Hamiltonian decomposition. This result, which is a special case of the

Oberwolfach problem The Oberwolfach problem is an unsolved problem in mathematics that may be formulated either as a problem of scheduling seating assignments for diners, or more abstractly as a problem in graph theory, on the edge cycle covers of complete graphs. I ...

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

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 group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

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

. 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-go-away-tournament) is a competition Competition is a rivalry where two or more parties strive for a common goal which cannot be shared: where one's gain is the other's loss (an example of which is a zero ...

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 Daniela Kühn (born 1973) is a German mathematician and the Mason Professor in Mathematics at the University of Birmingham in Birmingham, England.

and

Deryk Osthus Deryk Osthus is the Professor of Graph Theory at the School of Mathematics, University of Birmingham. He is known for his research in combinatorics, predominantly in extremal and probabilistic graph theory. Career Osthus earned a B.A. in mathemat ...

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 that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

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

. 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 In the mathematical discipline of graph theory, the medial graph of plane graph ''G'' is another graph ''M(G)'' that represents the adjacencies between edges in the faces of ''G''. Medial graphs were introduced in 1922 by Ernst Steinitz to study ...

of the

Herschel graph In graph theory, a branch of mathematics, the Herschel graph is a 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 does not have a Ha ...

Prisms

The ''prism'' over a graph is its

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...

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. , the conjecture remains unsolved. 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 into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of ...

, 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 In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways ...

of order divisible by four.

Symmetric graphs

There are infinitely many

vertex-transitive graph In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive i ...

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 that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayle ...

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.

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, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

, 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 mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

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

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 In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a ...

. 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 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...

have a Hamiltonian decomposition, and more strongly there is a

randomized polynomial time In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: * It always runs in polynomial time in the input size * If the correct ...

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

, 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 applicat ...

, series=Series B , mr = 3354297 , pages = 237–246 , title = Vertex-transitive graphs that have no Hamilton decomposition , volume = 114 , year = 2015, doi-access = free {{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 {{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 {{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 ''Discrete Mathematics & Theoretical Computer Science'' is a peer-reviewed open access scientific journal covering discrete mathematics and theoretical computer science. It was established in 1997 by Daniel Krob (Paris Diderot University). Since 2 ...

, mr = 3349112 , pages = 111–124 , title = Hamiltonian decomposition of prisms over cubic graphs , volume = 16 , year = 2014 {{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