2013/07/29 by Matt DeVos, DeVos, Matt, Jessica McDonald +3
Computer Science · Engineering · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques #math.CO #msc:05C70
paper · pdf · doi:10.48550/arxiv.1307.7621
38 pages, 4 figures
openalex publication_date 2013/07/29 · arxiv created 2015/08/07 · arxiv updated 2015/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let T be a distinguished subset of vertices in a graph G. A T-Steiner tree is a subgraph of G that is a tree and that spans T. Kriesell conjectured that G contains k pairwise edge-disjoint T-Steiner trees provided that every edge-cut of G that separates T has size ≥ 2k. When T=V(G) a T-Steiner tree is a spanning tree and the conjecture is a consequence of a classic theorem due to Nash-Williams and Tutte. Lau proved that Kriesell's conjecture holds when 2k is replaced by 24k, and recently West and Wu have lowered this value to 6.5k. Our main result makes a further improvement to 5k+4.