Vertex Connectivity of Graphs: Algorithms and Bounds

This report considers several problems concerning vertex connectivity of undirected graphs and presents new bounds and algorithms for these problems. Connectivity is one of the fundamental graph properties, and there has been a considerable amount of work on algorithms and structural aspects of this property. Applications of graph connectivity arise in operation research for scheduling problems, network analysis in electrical engineering, and many other real-life problems. The most direct application of this problem is for the reliability of networks. A fundamental criterion for evaluating performance of a communications network is its ability to withstand the failure of is not only real-life models but nonexistence of good upper bounds for the number of minimum size separating vertex sets of graphs. Another important measure of network reliability is to determine the subgraphs which are highly connected and to decompose the network into them. The results in all of these measures help in the design of optimum communication networks.