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


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].

See also


  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.