✦ LIBER ✦
Disproof of a conjecture about independent branchings in k-connected directed graphs
✍ Scribed by Andreas Huck
- Publisher
- John Wiley and Sons
- Year
- 1995
- Tongue
- English
- Weight
- 248 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
For each k ≥ 3, we construct a finite directed strongly k‐connected graph D containing a vertex t with the following property: For any k spanning t‐branchings, B~1~, …, B~k~ in D (i. e., each B~i~ is a spanning tree in D directed toward t), there exists a vertex x ≠ t of D such that the k, x, t‐paths in B~1~, …, B~k~ are not pairwise openly disjoint. This disproves a well‐known conjecture of Frank. © 1995, John Wiley & Sons, Inc.