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

Zap. Nauchn. Sem. POMI, 2006 Volume 340, Pages 76–86 (Mi znsl151)

Cliques in $k$-connected graphs

S. A. Obraztsova

Saint-Petersburg State Electrotechnical University

Abstract: The existance of $n+1$-cliques in $k$-connected graphs is studied. It is proved that in a $k$-connected graph $G$ such a clique exists provided $G$ satisfies the following conditions: (1) the vertices of any $n$-clique of $G$ lie in a $k$-separating set; (2) after removing certain pairs, each consisting of a vertex and an edge, the connectivity of the graph $G$ decreases by 2.

UDC: 519.171.1

Received: 20.09.2006


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

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025