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.
Type de document :
Article dans une revue
Combinatorica, Springer Verlag, 2007, 27 (6), pp.659-667. 〈10.1007/s00493-007-2073-3〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00256609
Contributeur : Stephan Thomasse <>
Soumis le : vendredi 15 février 2008 - 17:38:41
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : jeudi 20 mai 2010 - 22:17:38

Fichier

Identifiants

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〉

Partager

Métriques

Consultations de la notice

132

Téléchargements de fichiers

225