Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Hamiltonian decomposition
Summary
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.
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.
Every complete graph with an odd number 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 of the vertices into a regular polygon, and covers the complete graph in this subset of vertices with Hamiltonian paths that zigzag across the polygon, with each path rotated from each other path by a multiple of .
The paths can then all be completed to Hamiltonian cycles by connecting their ends through the remaining vertex.
Expanding a vertex of a -regular graph into a clique of 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.