Edge disjoint Steiner trees in graphs without large bridges
Matthias Kriesell · Journal of Graph Theory · 2009
Abstract A set A of vertices of an undirected graph G is called k‐edge‐connected in G if for all pairs of distinct vertices a, b∈A, there exist k edge disjoint a, b‐paths in G. An A‐tree is a subtree of G containing A, and an A‐bridge is a subgraph B of G which is either formed by a single edge with both end vertices in A or formed by the set of edges incident with the vertices of some component of G − A. It is proved that (i) if A is k·(ℓ + 2)‐edge‐connected in G and every A‐bridge has at most ℓ vertices in V(G) − A or at most ℓ + 2 vertices in A then there exist k edge disjoint A‐trees, and that (ii) if A is k‐edge‐connected in G and B is an A‐bridge such that B is a tree and every vertex in V(B) − A has degree 3 then either A is k‐edge‐connected in G − e for some e∈E(B) or A is (k − 1)‐edge‐connected in G − E(B). © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 188–198, 2009