Cyclability

Перейти к:навигация, поиск

Cyclabilityцикличность.

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$. It is known that if $\,G$ is a $\,3$-connected graph of 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\alpha (S,G) - 2$, then $\,S$ is cyclable. Here $\alpha (S,G)$ is the number of vertices of a maximum independent set of $\,G[S]$.