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

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

Панциклический граф (англ. 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]. Тогда верно одно из двух утверждений: [math] G [/math] — панциклический граф [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].

Ссылки

• Pancyclic Graphs I* J.A. Bondy