On the Structure of Minimum-Weight k -Connected Spanning Networks
Daniel A. Bienstock, Ernest F. Brickell, Clyde L. Monma · SIAM Journal on Discrete Mathematics · 1990
The problem of finding a minimum-weight k-connected spanning subgraph of a complete graph, assuming that the edge weights satisfy the triangle inequality, is studied. It is shown that the class of minimum-weight k-edge connected spanning subgraphs can be restricted to those subgraphs which, in addition to the connectivity requirements, satisfy the following two conditions: (I) Every vertex has degree k or $k + 1$; (II) Removing any $1, 2, \cdots ,$ or k edges does not leave the resulting connected components all k-edge connected. For the k-vertex connected case, the parallel result is obtained with “k-edge” replaced by “k-vertex,” with the added technical restriction that $| V |\geqq 2k$ for condition (I) to hold. This generalizes recent work of Monma, Munson, and Pulleyblank for the case $k = 2$.