Premium
Disproof of a conjecture about independent branchings in k ‐connected directed graphs
Author(s) -
Huck Andreas
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200212
Subject(s) - combinatorics , mathematics , conjecture , spanning tree , vertex (graph theory) , disjoint sets , graph , pairwise comparison , discrete mathematics , statistics
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.