On sparse subgraphs preserving connectivity properties
András Frank, Toshihide Ibaraki, Hiroshi Nagamochi · Journal of Graph Theory · 1993
Abstract From a theorem of W. Mader [“Über minimal n ‐fach zusammenhängende unendliche Graphen und ein Extremal problem,” Arch. Mat. , Vol. 23 (1972), pp. 553–560] it follows that a k ‐connected ( k ‐edge‐connected) graph G = ( V,E ) always contains a k ‐connected ( k ‐edge‐connected) subgraph G′ = ( V,E′ ) with O ( k | V |) edges. T. Nishizeki and S. Poljak “ K ‐Connectivity and Decomposition of Graphs into Forests,” Discrete Applied Mathematics, submitted) showed how G′ can be constructed as the union of k forests. H. Nagamochi and T. Ibaraki [A Linear Time Algorithm for Finding a Sparse k ‐Connected Spanning Subgraph of a k ‐Connected Graph, Algorithmica , Vol. 7 (1992), pp. 583–596] constructed such a subgraph G k in linear time and showed for any pair x,y of nodes that G k contains k openly disjoint (edge‐disjoint) paths connecting x and y if G contains k openly disjoint (edge‐disjoint) paths connecting x and y (even if G is not k ‐connected ( k ‐edge‐connected)). In this article we provide a much shorter proof of a common generalization of the edge‐ and node‐connectivity versions showing that the subgraph G k has a certain mixed connectivity property. © 1993 John Wiley & Sons, Inc.