Abstract
The vertex connectivity \(k(G)\) of a graph \(G\) is the minimum number of vertices whose removal results in a disconnected or trivial graph, that is, a graph with only one vertex. The edge connectivity \(\lambda(G)\) of a nontrivial graph \(G\) is the minimum number of edges whose removal results in a disconnected graph. It is known that the vertex connectivity \(k(G)\) of a graph \(G\) , the edge connectivity \(\lambda(G)\) , and the minimum vertex degree \(\delta(G)\) are related by the Whitney inequality \(k(G) \leq \lambda(G) \leq \delta(G)\) . Previously, the authors solved the problem of finding the minimum number of vertices and edges in graphs with given \(k(G)\) , \(\lambda(G)\) , and \(\delta(G)\) . The present paper continues this study and essentially uses its results. Formulas for the minimum number of vertices and edges in graphs with given \(k(G)\) and \(\lambda(G)\) are presented. Graphs with the minimum number of edges among all \(n\) -vertex graphs with given \(k(G)\) and \(\lambda(G)\) are considered. A family of such graphs with \(\lceil \lambda n/2 \rceil\) edges is described. A special case of this family for \(k=\lambda\) is the Harary graphs \(H_{k,n}\) , that is, \(n\) -vertex \(k\) -connected graphs with the minimum number of edges. It is known that the number of edges in such graphs equals \(\lceil k n/2 \rceil\) . The result is also related to the problem of determining the minimum number of edges in an \(n\) -vertex graph with given \(\lambda(G)\) , which was solved by Fulkerson and Shapley.
