✦ LIBER ✦
Covering a Strong Digraph by α−1 Disjoint Paths: A Proof of Las Vergnas' Conjecture
✍ Scribed by Stéphan Thomassé
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 83 KB
- Volume
- 83
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
The Gallai Milgram theorem states that every directed graph D is spanned by :(D) disjoint directed paths, where :(D) is the size of a largest stable set of D. When :(D)>1 and D is strongly connected, it has been conjectured by Las Vergnas that D is spanned by an arborescence with :(D)&1 leaves. The case :=2 follows from a result of C. C. Chen and P. Manalastas (1983, Discrete Math. 44, 243 250). We give a proof of this conjecture in the general case.