Edge-disjoint T-connectors

From Egres Open
Jump to: navigation, search

Let G=(V,E) be a graph, and [math]T \subseteq V[/math]. A T-connector is the union of a family of edge-disjoint paths in G with end-nodes in T, with the property that the end-node pairs of the paths in the family form a connected graph with node set T. Is it true that if T is 3k-edge-connected in G (i.e. there are 3k edge-disjoint paths between any two nodes of T), then G contains k edge-disjoint T-connectors?


This conjecture was formulated by Wu and West [1]. They proved that if T is 10k-edge-connected in G, then G contains k edge-disjoint T-connectors. This has been improved to 6k+6 by DeVos, McDonald, and Pivotto [2].


  1. D.B. West, H. Wu, Packing of Steiner trees and S-connectors in graphs, DOI link, Author link
  2. M. DeVos, J. McDonald, I. Pivotto, Packing Steiner Trees, DOI link, arXiv link