Optimal Graphs with Prescribed Connectivities
M. B. Abrosimov,
B. A. Terebin Saratov National Research State University
Abstract:
By the vertex connectivity
$k(G)$ of a graph
$G$ we mean the smallest number of vertices whose removal results in a disconnected or trivial graph, i.e., to a graph with one vertex. By the edge connectivity
$\lambda(G)$ of a nontrivial graph
$G$ we mean the smallest number of edges whose removal results in a disconnected graph. The vertex connectivity
$k(G)$, the edge connectivity
$\lambda(G)$, and the minimum vertex degree
$\delta(G)$ of a graph are related by the following inequality found by Whitney in 1932:
$k(G) \leq \lambda(G) \leq \delta(G)$.
More recently, Chartrand and Harary proved that for any positive integers
$a$,
$b$, and
$c$ such that
$0 < a \leq b \leq c$
there exists a graph
$G$ such that
$k(G)=a$,
$\lambda(G)=b$, and
$\delta(G)=c$. In the proof, one constructs a family of such graphs with
$2(c+1)$ vertices and
$c(c+1)+b$ edges each. However, it is easily seen that one can sometimes construct a suitable graph with fewer vertices and edges. For example, if
$a=b=c$, then the complete graph with
$c+ 1$ vertices is optimal. In the present paper, we consider the problem of minimizing the Chartrand–Harary construction. We show that for
$b=c$, it is possible to construct a graph with fewer vertices.
Four cases are considered separately:
$a=b=c$,
$a<b<c$,
$a=b<c$, and
$a<b=c$. For each case, we present graphs with the prescribed characteristics
$k(G)=a$,
$\lambda(G)=b$, and
$\delta(G)=c$ and with minimum numbers of vertices and edges.
Keywords:
connectivity, vertex connectivity, edge connectivity, minimum vertex degree, Whitney condition.
UDC:
519.17
MSC: 05C40 Received: 26.08.2022
Revised: 29.09.2022
DOI:
10.4213/mzm13517