On the optimality of graph implementations with prescribed connectivities

B. A. Terebin ; M. B. Abrosimov

Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 103-105

Résumé

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$.

Détail

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

Bibliographie

[1] Kharari F., Teoriya grafov, Mir, M., 1973, 300 pp. | MR

[2] Whitney H., “Congruent graphs and the connectivity of graphs”, Am. J. Math., 54 (1932), 150–168 | DOI | MR

[3] Chartrand G., Harary F., “Graphs with prescribed connectivities”, 1966 Symp. on Graph Theory. Tihany, Acad. Sci. Hung., 1967, 61–63 | MR