Combinatorica
Volume 27, Number 6, 659-667, DOI: 10.1007/s00493-007-2073-3

Spanning a strong digraph by α circuits: A proof of Gallai’s conjecture

Stéphane Bessy and Stéphan Thomassé

View Related Documents

Abstract

In 1963, Tibor Gallai [9] asked whether every strongly connected directed graph D is spanned by α directed circuits, where α is the stability of D. We give a proof of this conjecture.

Mathematics Subject Classification (2000)  05C20 - 05C38 - 05C69 - 05C70

Fulltext Preview

Image of the first page of the fulltext document