West–Wu's conjecture on packing T-connectors
West–Wu's conjecture on packing T-connectors
Let be a graph and a set of terminals. A -connector is the union of a family of edge-disjoint -paths such that, after shortcutting the paths one by one, the resulting graph has connected induced subgraph on . The set is -edge-connected in if no edge-cut of size smaller than separates two vertices of .
West–Wu's conjecture. For every positive integer , if is -edge-connected in , then admits pairwise edge-disjoint -connectors.
West and Wu introduced -connectors as a strengthening of Steiner trees. Their conjecture is refuted: the paper constructs infinitely many counterexamples for and for every even . DeVos, McDonald and Pivotto proved the conclusion under the stronger hypothesis that is -edge-connected in .
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Roman Čada, Adam Kabela, Tomáš Kaiser and Petr Vrána, “Packing T-connectors in graphs needs more connectivity”, arXiv:2308.07218 (2023).
Additional references
2 papers in this index state this conjecture (2013–2023). The statement above is taken from the most recent of them; the others are arXiv:1307.7621.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.