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

Zap. Nauchn. Sem. POMI, 2006 Volume 340, Pages 103–116 (Mi znsl153)

This article is cited in 1 paper

Removing vertices from $k$-connected graphs without losing $k$-connectivity

A. S. Chukhnov

Saint-Petersburg State University

Abstract: The problem of removing vertices from a $k$-connected graph without losing $k$-connectivity is studied. We prove that one can remove some inner vertices from $k$-blocks, provided the interior of each block is large enough with respect to its boundary and the degree of any vertex of the graph is greater than $\frac{3k-1}{2}$ or $\frac{3k}{2}$.

UDC: 519.172

Received: 19.12.2006


 English version:
Journal of Mathematical Sciences (New York), 2007, 145:3, 4989–4995

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024