Concept

Hamiltonian decomposition

Résumé
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
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées

Aucun résultat

Personnes associées

Aucun résultat

Unités associées

Aucun résultat

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement