Premium
On sparse subgraphs preserving connectivity properties
Author(s) -
Frank András,
Ibaraki Toshihide,
Nagamochi Hiroshi
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170302
Subject(s) - combinatorics , mathematics , disjoint sets , vertex connectivity , graph , discrete mathematics , connectivity , connected component , disjoint union (topology) , enhanced data rates for gsm evolution , computer science , vertex (graph theory) , telecommunications
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.