Показатель краткости

В теории графов показатель краткости — это числовой параметр семейства графов, который измеряет, насколько далекими от гамильтониана могут быть графы в семействе. Интуитивно, если $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.