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

Zap. Nauchn. Sem. POMI, 2010 Volume 381, Pages 88–96 (Mi znsl3854)

This article is cited in 4 papers

Local structure of 5 and 6-connected graphs

S. A. Obraztsova

St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: We prove, that if graph on $n$ vertices is mimimally and contraction critically 5-connected, then it has $4n/7$ vertices of degree 5. We also prove, that if graph on $n$ vertices is mimimally and contraction critically 6-connected, then it has $n/2$ vertices of degree 6. Bibl. 7 titles.

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

UDC: 519.173.1

Received: 15.07.2010


 English version:
Journal of Mathematical Sciences (New York), 2011, 179:5, 621–625

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025