Skip to Main content Skip to Navigation
Journal articles

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

Stéphane Bessy 1 Stéphan Thomassé 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00256609
Contributor : Stephan Thomasse <>
Submitted on : Friday, February 15, 2008 - 5:38:41 PM
Last modification on : Thursday, February 7, 2019 - 5:14:10 PM
Document(s) archivé(s) le : Thursday, May 20, 2010 - 10:17:38 PM

Identifiers

Collections

Citation

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

Share

Metrics

Record views

199

Files downloads

373