Cyclability

Материал из WikiGrapp
Версия от 15:29, 18 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Cyclability''' --- цикличность. A subset <math>S</math> of vertices of a graph <math>G</math> is called '''cyclable''' in <math>G</math> if there is …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

A subset [math]\displaystyle{ S }[/math] of vertices of a graph [math]\displaystyle{ G }[/math] is called cyclable in [math]\displaystyle{ G }[/math] if there is in [math]\displaystyle{ G }[/math] some cycle containing all the vertices of [math]\displaystyle{ S }[/math]. It is known that if [math]\displaystyle{ G }[/math] is a 3-connected graph of order [math]\displaystyle{ n }[/math] and if [math]\displaystyle{ S }[/math] is a subset of vertices such that the degree sum of any four independent vertices of [math]\displaystyle{ S }[/math] is at least [math]\displaystyle{ n + 2\alpha (S,G) - 2 }[/math], then [math]\displaystyle{ S }[/math] is cyclable. Here [math]\displaystyle{ \alpha (S,G) }[/math] is the number of vertices of a maximum independent set of [math]\displaystyle{ G[S] }[/math].

See also

  • Pancyclable graph.