|
Zapiski Nauchnykh Seminarov 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.
Received: 01.11.2020
Citation:
N. A. Karol', “Criterion for the existence of such a cycle that vertices beyond this cycle are independent”, Combinatorics and graph theory. Part XII, Zap. Nauchn. Sem. POMI, 497, POMI, St. Petersburg, 2020, 53–79
Linking options:
https://www.mathnet.ru/eng/znsl7027 https://www.mathnet.ru/eng/znsl/v497/p53
|
Statistics & downloads: |
Abstract page: | 70 | Full-text PDF : | 21 | References: | 16 |
|