RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2011 Volume 391, Pages 157–197 (Mi znsl4572)

This article is cited in 2 papers

Local structure of 9 and 10-connected graphs

S. A. Obraztsova

Nanyang Technological University, Singapore

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.

UDC: 519.173.1

Received: 12.10.2011


 English version:
Journal of Mathematical Sciences (New York), 2012, 184:5, 634–654

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025