Criterion for the existence of such a cycle that vertices beyond this cycle are independent
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XII, Tome 497 (2020), pp. 53-79
Citer cet article
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
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.
[1] J. A. Bondy, U. S. R. Murty, Graph Theory With Applications, Elsevier Science, 1976 | MR | Zbl
[2] R. Diestel, Graph Theory, izdaniya 1–5, Springer, 1997–2016 | MR | Zbl
[3] N. Linial, “A lower bound on the circumference of a graph”, Discrete Math., 15 (1976), 297–300 | DOI | MR | Zbl
[4] S. Thomassen, “A theorem on paths in planar graphs”, J. Graph Theory, 7 (1983), 169–176 | DOI | MR | Zbl