Панциклический граф

Материал из Викиконспекты
Версия от 19:36, 24 ноября 2017; Alex PKZDL (обсуждение | вклад) (Начало положено)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Панциклический граф (англ. pancyclic graph) — граф, в котором есть циклы всех длин от [math] 3 [/math] до [math] n [/math] . Если граф содержит все циклы от [math] r [/math] до [math] n [/math], то такой граф называют [math] r [/math]-панциклическим.


Теорема (J. A. Bondy):
[math]G = \lt V, E\gt [/math] — гамильтонов граф, [math]|V| = n, |E| \geq n^2/4 [/math].

Тогда верно одно из двух утверждений:

  1. [math] G [/math] — панциклический граф
  2. [math] G [/math] = [math]K_{n / 2, n / 2}[/math]


Теорема (Schmeichel & Hakimi):
[math]G = \lt V, E\gt [/math] — гамильтонов граф, [math]|V| = n, v_1 v_2 v_3 \ldots v_n v_1 [/math] — его гамильтонов цикл, для которого выполняется неравенство [math] deg(v_1) + deg(v_n) \geq n [/math].
Тогда [math] G [/math] — панциклический граф, двудольный граф или граф, в котором нет только цикла длины [math](n-1)[/math].


Ссылки