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

Zap. Nauchn. Sem. POMI, 2020 Volume 497, Pages 53–79 (Mi znsl7027)

Criterion for the existence of such a cycle that vertices beyond this cycle are independent

N. A. Karol'

New Economic School

Abstract: This paper contains a criterion for the existence of such a cycle that the vertices beyond this cycle are independent in terms of minimum vertex degree. More specifically, if $G$ is a $2$-connected graph, $v(G) = n$ and $\delta(G) \geq \frac{n + 2}{3}$, then $G$ has a cycle such that vertices beyond this cycle are independent.

Key words and phrases: independent set, biconnected graph, minimum degree.

UDC: 519.17

Received: 01.11.2020



© Steklov Math. Inst. of RAS, 2024