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

Показатель короткости — это числовой параметр семейства графов, который показывает, насколько далеки от гамильтоновости могут быть графы семейства. Интуитивно, если ${\displaystyle e}$ является показателем короткости графа семейства ${\displaystyle {\mathcal {F}}}$, тогда любой граф с ${\displaystyle n}$ вершинами имеет цикл длины, близкой к ${\displaystyle n^{e}}$, но некоторые графы не имеют более длинные циклы. Более точно, для любого упорядочения графов в ${\displaystyle {\mathcal {F}}}$ в последовательность ${\displaystyle G_{0},G_{1},\dots }$, и функции ${\displaystyle h(G)}$, определённой как длина наибольшего цикла в графе ${\displaystyle G}$, показатель короткости определяется как[1]

${\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})}$[2], и было также доказано, что любой полиэдральный граф содержит цикл, длиной ${\displaystyle \Omega (n^{\log _{3}2})}$[3]. Полиэдральные графы — это графы, которые одновременно являются планарными и вершинно 3-связными. Факт вершинной 3-связности здесь важен, поскольку существует множество вершинно 2-связных планарных графов (таких как полные двудольные графы ${\displaystyle K_{2,n}}$) с показателем короткости 0. Есть много дополнительных результатов относительно показателя короткости ограниченных подклассов планарных и полиэдральных графов[1].

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