Disproof of a conjecture about independent branchings in  k ‐connected directed graphs | Zendy

Huck Andreas | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research