Edge-disjoint T-connectors
From Egres Open
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?
Counterexamples for k=1 and for every even k have been found by Čada, Kabela, Kaiser, and Vrána [1].
Remarks
This conjecture was formulated by Wu and West [2]. 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 [3].
References
- ↑ R. Čada, A. Kabela, T. Kaiser, P. Vrána, Packing T-connectors in graphs needs more connectivity, 2023, arXiv link
- ↑ D.B. West, H. Wu, Packing of Steiner trees and S-connectors in graphs, DOI link, Author link
- ↑ M. DeVos, J. McDonald, I. Pivotto, Packing Steiner Trees, DOI link, arXiv link
