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

Определение:

Панциклический граф (англ. 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| \geqslant n^2/4 [/math]. Тогда верно одно из двух утверждений: [math] G [/math] — панциклический граф [math] G [/math] = [math]K_{n / 2, n / 2}[/math]

Доказательство:

[math]\triangleright[/math]

Обозначим как [math] C=v_1 v_2 v_3 \ldots v_n [/math] гамильтонов цикл в графе [math] G [/math]. Для простоты расположим [math] C [/math] на окружности, тогда ребра не принадлежащие [math] C [/math] можно считать хордами. Пусть в графе нет цикла длины [math] l [/math], [math] 3 \leqslant l \leqslant n-1 [/math] (по условию в графе существует гамильтонов цикл, длина которого равна [math] n [/math]). Рассмотрим две соседний вершины в [math] v_i v_{i+1} [/math] [math] j + l - 1 \leqslant k \leqslant j + l - 2 [/math] [math] j + 2 \leqslant k \leqslant j + l - 2 [/math]

[math]\triangleleft[/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].

Ссылки

• Pancyclic Graphs I* J.A. Bondy