Показник короткості

Показник короткості — це числовий параметр сімейства графів, який показує, наскільки далекими від гамільтоновості можуть бути графи сімейства. Інтуїтивно, якщо $e$ — показник короткості графа сімейства ${\mathcal {F}}$, то будь-який граф із $n$ вершинами має цикл довжини, близької до $n^{e}$ але деякі графи не мають довших циклів. Точніше, для будь-якого впорядкування графів у ${\mathcal {F}}$ у послідовність $G_{0},G_{1},\dots$, та функції $h(G)$, визначеної як довжина найбільшого циклу в графі $G$, показник короткості визначають як

$\liminf _{i\to \infty }{\frac {\log h(G_{i})}{\log |V(G_{i})|}}.$

Це число завжди міститься в інтервалі від 0 до 1. Показник дорівнює 1, якщо графи сімейства завжди містять гамільтонів або близький до гамільтонового цикл, і 0, якщо найбільша довжина циклів у графах сімейства може бути меншою від будь-якого сталого степеня числа вершин.

Показник короткості поліедральних графів дорівнює $\log _{3}2\approx 0,631$. Побудова, заснована на многогранниках Клі, показує, що деякі поліедральні графи мають найбільший цикл завдовжки $O(n^{\log _{3}2})$, і було також доведено, що будь-який поліедральний граф містить цикл, довжиною $\Omega (n^{\log _{3}2})$. Поліедральні графи — це графи, які одночасно є планарними і вершинно 3-зв'язними. Факт вершинної 3-зв'язності тут важливий, оскільки існує множина вершинно 2-зв'язних планарних графів (таких як повні двочасткові графи $K_{2,n}$) із показником короткості 0. Є багато додаткових результатів щодо показника короткості обмежених підкласів планарних та поліедральних графів.

Вершинно 3-зв'язні кубічні графи (без вимог планарності) також мають показник короткості, який (як було показано) лежить строго між 0 і 1.

Література

• Branko Grünbaum, Hansjoachim Walther. Shortness exponents of families of graphs // Journal of Combinatorial Theory. — 1973. — Т. 14. — С. 364–385. — (Series A). — DOI:10.1016/0097-3165(73)90012-5.
• J. W. Moon, L. Moser. Simple paths on polyhedra // Pacific Journal of Mathematics. — 1963. — Т. 13. — С. 629–631.
• Guantao Chen, Xingxing Yu. Long cycles in 3-connected graphs // Journal of Combinatorial Theory. — 2002. — Т. 86, вип. 1. — С. 80–99. — (Series B). — DOI:10.1006/jctb.2002.2113.
• J. A. Bondy, M. Simonovits. Longest cycles in 3-connected 3-regular graphs // Canadian Journal of Mathematics. — 1980. — Т. 32, вип. 4. — С. 987–992. — DOI:10.4153/CJM-1980-076-2.
• Bill Jackson. Longest cycles in 3-connected cubic graphs // Journal of Combinatorial Theory. — 1986. — Т. 41, вип. 1. — С. 17–26. — (Series B). — DOI:10.1016/0095-8956(86)90024-9.