4194
правки
Cyclability: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
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 …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Cyclability''' --- | '''Cyclability''' — ''[[цикличность]]''. | ||
A subset <math>\,S</math> of [[vertex|vertices]] of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is called '''cyclable''' in | |||
<math>\,G</math> if there is in <math>\,G</math> some cycle containing all the vertices of <math>\,S</math>. | |||
It is known that if <math>\,G</math> is a [[k-Connected graph|<math>\,3</math>-connected graph]] of order <math>\,n</math> and if <math>\,S</math> | |||
is a subset of vertices such that the degree sum of any four independent vertices of <math>\,S</math> is at least <math>\,n + 2\alpha (S,G) - 2</math>, then <math>\,S</math> is cyclable. Here <math>\alpha (S,G)</math> is the number of vertices of a maximum independent set of <math>\,G[S]</math>. | |||
==See also== | ==See also== | ||
*''Pancyclable graph''. | |||
* ''[[Pancyclic graph|Pancyclable graph]]''. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||