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 Access content directly
Journal Articles Combinatorica Year : 2007

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

Stéphane Bessy
Stéphan Thomassé

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.
Fichier principal
Vignette du fichier
gallai.pdf (136.92 Ko) Télécharger le fichier
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
92 View
348 Download

Altmetric

Share

Gmail Facebook X LinkedIn More