On minimally k-edge-connected graphs and shortest k-edge-connected Steiner networks

摘要

A graph G = (V, E) is called minimally (k, T)-edge-connected with respect to some T is contained in V if there exist k-edge-disjoint paths between every pair u, ν ∈ T but this property fails by deleting any edge of G. We show that |V| can be bounded by a (linear) function of k and |T| if each vertex in V-T has odd degree. We prove similar bounds in the case when G is simple and k ≤ 3. These results are applied to prove structural properties of optimal solutions of the shortest k-edge-connected Steiner network problem. We also prove lower bounds on the corresponding Steiner ratio.