×

Connectivity and edge-connectivity in graphs: A survey. (English) Zbl 0905.05044

This expository article reviews the basic notions of connectivity and edge-connectivity of finite, undirected, simple graphs and discusses the efficiency of computing these two parameters. Bounds on these parameters are considered as well as some of their variants. A number of “Menger-type” theorems are cited, i.e., characterizations of a separation property in terms of the maximum number of edge-disjoint or internally vertex-disjoint paths joining some or all pairs of vertices of a given graph.

MSC:

05C40 Connectivity
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDFBibTeX XMLCite