Geodesic
One family of optimal graphs with prescribed connectivities
Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 116-119 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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$.
Keywords: graph, vertex connectivity, edge connectivity, fault tolerance. 
@article{PDMA_2022_15_a27,
     author = {B. A. Terebin and M. B. Abrosimov},
     title = {One family of optimal graphs with prescribed connectivities},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {116--119},
     year = {2022},
     number = {15},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2022_15_a27/}
}
TY  - JOUR
AU  - B. A. Terebin
AU  - M. B. Abrosimov
TI  - One family of optimal graphs with prescribed connectivities
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2022
SP  - 116
EP  - 119
IS  - 15
UR  - http://geodesic.mathdoc.fr/item/PDMA_2022_15_a27/
LA  - ru
ID  - PDMA_2022_15_a27
ER  - 
%0 Journal Article
%A B. A. Terebin
%A M. B. Abrosimov
%T One family of optimal graphs with prescribed connectivities
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2022
%P 116-119
%N 15
%U http://geodesic.mathdoc.fr/item/PDMA_2022_15_a27/
%G ru
%F PDMA_2022_15_a27
B. A. Terebin; M. B. Abrosimov. One family of optimal graphs with prescribed connectivities. Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 116-119. http://geodesic.mathdoc.fr/item/PDMA_2022_15_a27/

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

[2] Harary F., “The maximum connectivity of a graph”, Proc. NAS USA, 48 (1962), 1142–1146 | DOI | MR | Zbl

[3] Chartrand G. and Harary F., “Graphs with prescribed connectivities”, Theory of Graphs, Academic Press, N.Y., 1968, 61–63 | MR

[4] Steiglitz K., Weiner P., and Kleitman D., “The design of minimum-cost survivable networks”, IEEE Trans. Circuit Theory, 16:4 (1969), 455–460 | DOI | MR

[5] Jafarpour M., Shekaramiz M., Javan A., and Moeini A., “Building graphs with maximum connectivity”, Proc. IETS, 2020, 1–5

[6] Kharari F., Teoriya grafov, Mir, M., 1973

[7] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997 | MR

[8] Terebin B. A., Abrosimov M. B., “Ob optimalnosti realizatsii grafov s zadannymi merami svyaznosti”, Prikladnaya diskretnaya matematika. Prilozhenie, 2020, no. 13, 103–105

[9] Terebin B. A., Abrosimov M. B., “O minimalnom chisle reber v realizatsiyakh grafov s zadannymi merami svyaznosti”, Kompyuternye nauki i informatsionnye tekhnologii, Materialy Mezhdunar. nauch. konf., 2021, 159–161