Packing Steiner trees

详细信息    查看全文

• 作者：Matt DeVos^a ; ¹ ; ^{mdevos@sfu.ca" class="auth_mail" title="E-mail the corresponding author} ; Jessica McDonald^b ; ^{mcdonald@auburn.edu" class="auth_mail" title="E-mail the corresponding author} ; Irene Pivotto^c ; ² ; ^{irene.pivotto@uwa.edu.au" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Steiner trees ; Packing
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：119
• 期：Complete
• 页码：178-213
• 全文大小：672 K

文摘

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$\ge 2k$. When T=V(G)$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$5k+4$.