ABSTRACT
Camino Balbuena, Universitat Polite`cnica de Catalunya, Spain Josep Fa`brega, Universitat Polite`cnica de Catalunya, Spain
Miquel A`ngel Fiol, Universitat Polite`cnica de Catalunya, Spain
4.1.1 Connectivity Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
4.1.2 Characterizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
4.1.3 Structural Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
4.1.4 Analysis and Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
INTRODUCTION
Connectivity is one of the central concepts of graph theory, from both a theoretical and a practical point of view. Its theoretical implications are mainly based on the existence of nice max-min characterization results, such as Menger’s theorems. In these theorems, one condition which is clearly necessary also turns out to be sufficient. Moreover, these results are closely related to some other key theorems in graph theory: Ford and Fulkerson’s theorem about flows and Hall’s theorem on perfect matchings. With respect to the applications, the study of connectivity parameters of graphs and digraphs is of great interest in the design of reliable and fault-tolerant interconnection or communication networks.
