Geodesic
Optimal Graphs with Prescribed Connectivities
Matematičeskie zametki, Tome 113 (2023) no. 3, pp. 323-331.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$, $a=b$, and $a$. 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. 
@article{MZM_2023_113_3_a0,
     author = {M. B. Abrosimov and B. A. Terebin},
     title = {Optimal {Graphs} with {Prescribed} {Connectivities}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {323--331},
     publisher = {mathdoc},
     volume = {113},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2023_113_3_a0/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - B. A. Terebin
TI  - Optimal Graphs with Prescribed Connectivities
JO  - Matematičeskie zametki
PY  - 2023
SP  - 323
EP  - 331
VL  - 113
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2023_113_3_a0/
LA  - ru
ID  - MZM_2023_113_3_a0
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A B. A. Terebin
%T Optimal Graphs with Prescribed Connectivities
%J Matematičeskie zametki
%D 2023
%P 323-331
%V 113
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2023_113_3_a0/
%G ru
%F MZM_2023_113_3_a0
M. B. Abrosimov; B. A. Terebin. Optimal Graphs with Prescribed Connectivities. Matematičeskie zametki, Tome 113 (2023) no. 3, pp. 323-331. http://geodesic.mathdoc.fr/item/MZM_2023_113_3_a0/

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

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

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

[4] G. Chartrand, F. Harary, “Graphs with prescribed connectivities”, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, 61–63 | MR

[5] B. A. Terebin, M. B. Abrosimov, “Ob optimalnosti realizatsii grafov s zadannymi merami svyaznosti”, Prikladnaya diskretnaya matematika. Prilozhenie, Izdatelskii dom TGU, Tomsk, 2020, 103–105

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