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

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

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

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

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

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

Примітки

1. Grünbaum, Walther, 1973, с. 364–385.
2. Moon, Moser, 1963, с. 629–631.
3. Chen, Yu, 2002, с. 80–99.
4. Bondy, Simonovits, 1980, с. 987–992.
5. Jackson, 1986, с. 17–26.

Література

• Branko Grünbaum, Hansjoachim Walther. Shortness exponents of families of graphs // . — 1973. — Т. 14. — С. 364–385. — (Series A). — DOI:10.1016/0097-3165(73)90012-5.
• J. W. Moon, L. Moser. Simple paths on polyhedra // . — 1963. — Т. 13. — С. 629–631.
• Guantao Chen, Xingxing Yu. Long cycles in 3-connected graphs // . — 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 // . — 1980. — Т. 32, вип. 4. — С. 987–992. — DOI:10.4153/CJM-1980-076-2.
• Bill Jackson. Longest cycles in 3-connected cubic graphs // . — 1986. — Т. 41, вип. 1. — С. 17–26. — (Series B). — DOI:10.1016/0095-8956(86)90024-9.