One family of optimal graphs with prescribed connectivities

B. A. Terebin ; M. B. Abrosimov

Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 116-119

Résumé

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. 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 $\lambda$, we describe the graphs that, for a given $n$, have the minimum number of edges $\lceil {\lambda n}/{2} \rceil$. The corresponding graph is either regular of order $\lambda$ or has one vertex of degree $\lambda + 1$, and the remaining vertices of degree $\lambda$.

Détail

Keywords: graph, vertex connectivity, edge connectivity, fault tolerance.