短さ指数

グラフ理論において、短さ指数はグラフ族の数値パラメータであり、そのグラフ族内のグラフがハミルトングラフからどれだけ離れているかを測定する。直感的には、${\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 ]}