One family of optimal graphs with prescribed connectivities

The vertex connectivity k is the smallest number of vertices whose removal leads to a disconnected or trivial graph. The edge connectivity of a nontrivial graph is the smallest number of edges whose removal leads to a disconnected graph. In this paper, we study n-vertex graphs that are minimal in terms of the number of edges and have given values of vertex and edge connectivity. In addition to theoretical interest, graphs with given values of vertex or edge connectivity are also of applied interest as models of fault-tolerant networks. The main result is that, for a certain range of values of k and , we describe the graphs that, for a given n, have the minimum number of edges d n=2e. The corresponding graph is either regular of order or has one vertex of degree + 1, and the remaining vertices of degree .

Keywords

Authors

References