Cycles intersecting a prescribed vertex set
Atsushi Kaneko, Akira Saito · Journal of Graph Theory · 1991
Abstract A graph is said to have property P(k,l)(k ⩾ l) if for any X ∈ (Gk) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n‐connected graph (n ⩾ 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n‐connected graph satisfies P(k,l). We show that for r = 1 or 2 every n‐connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3‐connected graphs that do not satisfy P(6,3). However, if n ⩾ max{3,(2r −1)(r + 1)}, then every n‐connected graph satisfies P(n + r,n).