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.
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 of vertices has a Hamiltonian decomposition. This result, which is a special case of the Oberwolfach problem of decomposing complete graphs into isom

Official source

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.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications

Related concepts

Related units

No results

No results

No results

Related people

No results

Related lectures

Related courses

No results

No results