Abstract:
In his paper R. Halin (in “Recent Progress in Combinatorics”, Academic Press, 1969) discusses, what is the constant $c_k$ such that any minimally and contraction critically $k$-connected graph has at least $c_k|V(G)|$ vertices of degree $k$. Twenty years later the exact bound for $k=4$ ($c_4=1$) was found by N. Martinov and, independently, by M. Fontet. For larger $k$ exact bounds are unknown.
This paper contributes to the study of local structure of minimally and contraction critically $k$-connected graphs and lower bounds for $c_k$. It was proved that $c_k\geq\frac12$ for $k=9,10$. This result extends the sequence of the lower bounds for $c_k$ which is equal to $\frac12$ to $k=6,7,8,9,10$.
Key words and phrases:$k$-connectivity, minimally $k$-connected, contraction critically $k$-connected, lower bounds.