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

Zap. Nauchn. Sem. POMI, 2011 Volume 391, Pages 198–210 (Mi znsl4573)

This article is cited in 2 papers

About vertices of degree $k$ of minimally and contraction critically $k$-connected graphs: upper bounds

S. A. Obraztsovaa, A. V. Pastorb

a Nanyang Technological University, Singapore
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: In the article [4], R. Halin asked, what 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$. Exact bound for $k=4$ ($c_4=1$) and no upper bound for larger $k$ is known now. We found upper bounds for $c_k$ for $k\geq5$.

Key words and phrases: $k$-connectivity, minimally $k$-connected, contraction critically $k$-connected, upper bounds.

UDC: 519.173.1

Received: 29.08.2011


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

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024