RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2020 Issue 13, Pages 103–105 (Mi pdma510)

This article is cited in 3 papers

Applied Theory of Coding, Automata and Graphs

On the optimality of graph implementations with prescribed connectivities

B. A. Terebin, M. B. Abrosimov

Saratov State University

Abstract: Connected graphs are of great interest in applications, i.e., in design of reliable systems. The vertex connectivity $k$ of a graph $G$ is the minimum number of vertices whose removal leads to a disconnected or trivial graph. Analogously, the edge connectivity $\lambda$ of a graph $G$ is the minimum number of edges whose removal leads to a disconnected or trivial graph. They are related with the minimum vertex degree $\delta$ by Whitney inequality: $k \leq \lambda \leq \delta$. G. Chartrand and F. Harary proved that this result is not improving in the sense that for any natural numbers $a, b, c$, such that $0 < a \leq b \leq c$, we can construct a graph for which $k = a$, $\lambda = b$, $\delta = c$. In their proof, Chartrand and Harary proposed the graph with the number of vertices $2(c + 1)$ and the number of edges $c(c + 1) + b$, and the prescribed values of vertex connection, edge connection, and the minimum degree of vertices. In this paper, we consider the problem of constructing the corresponding implementation with the smallest possible number of vertices and edges. Main results: if $a \leq b < c$, then the minimun number of vertices is $2(c + 1)$, if $a = b = c$, then it is $c + 1$, and if $a \leq b = c$, then the minimum number of vertices is $2(c+1) - a$.

Keywords: vertex connectivity, edge connectivity, Whitney's inequality.

UDC: 519.17

DOI: 10.17223/2226308X/13/30



© Steklov Math. Inst. of RAS, 2024