Spanning a strong digraph by $\alpha$ circuits: A proof of Gallai's conjecture - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Combinatorica Année : 2007

Spanning a strong digraph by $\alpha$ circuits: A proof of Gallai's conjecture

Stéphane Bessy
Stéphan Thomassé

Résumé

In 1963, Tibor Gallai~\cite{TG} asked whether every strongly connected directed graph $D$ is spanned by $\alpha$ directed circuits, where $\alpha$ is the stability of $D$. We give a proof of this conjecture.
Fichier principal
Vignette du fichier
gallai.pdf (136.92 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00256609 , version 1 (15-02-2008)

Identifiants

Citer

Stéphane Bessy, Stéphan Thomassé. Spanning a strong digraph by $\alpha$ circuits: A proof of Gallai's conjecture. Combinatorica, 2007, 27 (6), pp.659-667. ⟨10.1007/s00493-007-2073-3⟩. ⟨lirmm-00256609⟩
103 Consultations
372 Téléchargements

Altmetric

Partager

More