Geodesic
Minimal $k$-connected graphs with minimal number of vertices of degree $k$
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 41-65 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A graph is $k$-connected if it has at least $k+1$ vertices and remains connected after deleting any its $k-1$ vertices. A $k$-connected graph is called minimal, if it becomes not $k$-connected after deleting any edge. W. Mader has proved that any minimal $k$-connected graph on $n$ vertices has at least $\frac{(k-1)n+2k}{2k-1}$ vertices of degree $k$. We prove that any minimal $k$-connected graph with minimal number of vertices of degree $k$ is a graph $G_{k,T}$ for some tree $T$ with vertex degrees at most $k+1$. The graph $G_{k,T}$ is constructed from $k$ disjoint copies of the tree $T$. For any vertex $a$ of the tree $T$ we denote by $a_1,\dots,a_k$ the correspondent vertices of copies of $T$. If the vertex $a$ has degree $j$ in the tree $T$ then we add $k+1-j$ new vertices of degree $k$ which are adjacent to $\{a_1,\dots,a_k\}$. 
@article{ZNSL_2014_427_a2,
     author = {D. V. Karpov},
     title = {Minimal $k$-connected graphs with minimal number of vertices of degree~$k$},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {41--65},
     year = {2014},
     volume = {427},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a2/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - Minimal $k$-connected graphs with minimal number of vertices of degree $k$
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2014
SP  - 41
EP  - 65
VL  - 427
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a2/
LA  - ru
ID  - ZNSL_2014_427_a2
ER  - 
%0 Journal Article
%A D. V. Karpov
%T Minimal $k$-connected graphs with minimal number of vertices of degree $k$
%J Zapiski Nauchnykh Seminarov POMI
%D 2014
%P 41-65
%V 427
%U http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a2/
%G ru
%F ZNSL_2014_427_a2
D. V. Karpov. Minimal $k$-connected graphs with minimal number of vertices of degree $k$. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 41-65. http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a2/

[1] G. A. Dirac, “Minimally $2$-connected graphs”, J. Reine and Angew. Math., 268 (1967), 204–216 | MR

[2] M. D. Plummer, “On minimal blocks”, Trans. Amer. Math. Soc., 134 (1968), 85–94 | DOI | MR | Zbl

[3] W. T. Tutte, Connectivity in graphs, Univ. Toronto Press, Toronto, 1966 | MR | Zbl

[4] W. Mader, “Ecken Vom Gard $n$ in minimalen $n$-fach zusammenhangenden Graphen”, Arch. Math. (Basel), 23 (1972), 219–224 | DOI | MR | Zbl

[5] W. Mader, “On vertices of degree $n$ in minimally $n$-connected graphs and digraphs”, Combinatorics, Paul Erdös is Eighty, v. 2, Budapest, 1996, 423–449 | MR | Zbl

[6] W. Mader, “Zur Struktur minimal n-fach zusammenhängender Graphen”, Abh. Math. Sem. Univ. Hamburg, 49 (1979), 49–69 | DOI | MR | Zbl

[7] J. G. Oxley, “On some extremal connectivity results for graphs and matroids”, Discrete Math., 41 (1982), 181–198 | DOI | MR | Zbl

[8] D. V. Karpov, A. V. Pastor, “Struktura razbieniya trekhsvyaznogo grafa”, Zap. nauchn. semin. POMI, 391, 2011, 90–148 | MR

[9] D. V. Karpov, “Razdelyayuschie mnozhestva v $k$-svyaznom grafe”, Zap. nauchn. semin. POMI, 340, 2006, 33–60 | MR | Zbl

[10] D. V. Karpov, “Minimalnye dvusvyaznye grafy”, Zap. nauchn. semin. POMI, 417, 2013, 106–127