Minimal $k$-connected graphs with minimal number of vertices of degree~$k$

D. V. Karpov

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 41-65

Résumé

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