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

Показатель короткости — это числовой параметр семейства графов, который показывает, насколько далеки от гамильтоновости могут быть графы семейства. Интуитивно, если $e$ является показателем короткости графа семейства $ℱ$, тогда любой граф с $n$ вершинами имеет цикл длины, близкой к $n^e$, но некоторые графы не имеют более длинные циклы. Более точно, для любого упорядочения графов в $ℱ$ в последовательность $G_0,G_1,\dots$, и функции $h(G)$, определённой как длина наибольшего цикла в графе $G$, показатель короткости определяется какШаблон:Sfn

$\underset{i\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{\log h(G_i)}{\log |V(G_i)|}.$

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья