Applied Graph Theory

Optimal graphs with a cut vertex and given edge connectivity

B. A. Terebin, M. B. Abrosimov

Saratov State University, Saratov, Russia

Abstract: The vertex connectivity $k$ is the smallest number of vertices whose removal leads to a disconnected or trivial graph. The edge connectivity $\lambda$ of a nontrivial graph is the smallest number of edges whose removal leads to a disconnected graph. D. Fulkerson and L. Shapley solved the problem of determining the minimum number of edges in a graph with a given number of vertices $n$ and a given edge connectivity $\lambda$. In this paper, we study the minimal $n$-vertex graphs with given values of vertex and edge connectivity. The main result is that we determine the minimum number of edges that $n$-vertex graphs with an articulation point and a given edge connectivity $\lambda > 1$ can have: $[ (\lambda n + \lambda + 1)/2 ]$. A scheme for constructing graphs with such a number of edges is proposed. This is always possible for $n \geq 2\lambda$.

Keywords: graph, vertex connectivity, edge connectivity.

UDC: 519.17

DOI: 10.17223/20710410/70/4