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

Stéphane Bessy; Stéphan Thomassé

doi:10.1007/s00493-007-2073-3

Back

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

Journal article

Open access

Peer reviewed

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

Stéphane Bessy and Stéphan Thomassé

Combinatorica, Vol.27(6), pp.659-667

2007

DOI: https://doi.org/10.1007/s00493-007-2073-3

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.

Files and links (1)

url

Find in HALView

Metrics

1 Record Views

Details

Title: Spanning a strong digraph by $\alpha$ circuits: A proof of Gallai's conjecture
Creators - without role: Stéphane Bessy - Université de Montpellier
Stéphan Thomassé - Université de Montpellier
Publication Details: Combinatorica, Vol.27(6), pp.659-667
Identifiers: 9947218909311
Academic Unit: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Language: English
Resource Type: Journal article
Local Fields: lirmm-00256609