Cyclability of 3-connected graphs
Amel Harkat-Benhamdine, Hao Li, Feng Tian · Journal of Graph Theory · 2000
A subset S of vertices of a graph G is called cyclable in G if there is in G some cycle containing all the vertices of S. We denote by α(S, G) the number of vertices of a maximum independent set of G[S]. We prove that if G is a 3-connected graph or order n and if S is a subset of vertices such that the degree sum of any four independent vertices of S is at least n + 2α(S, G) −2, then S is cyclable. This result implies several known results on cyclability or Hamiltonicity. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 191–203, 2000