度直径問題

グラフ理論において、次数直径問題とは、Gの頂点の最大次数がd以下となるような直径kの最大のグラフ G (頂点集合Vのサイズに関して)を見つける問題である。G のサイズはムーアの限界によって制限される。1 < kおよび2 < dの場合、ピーターセングラフ、ホフマンシングルトングラフ、およびおそらく直径k = 2および次数d = 57のグラフ (まだ存在が証明されていない)のみがムーアの限界に達する。一般に、最大次数直径グラフのサイズはムーアの限界よりもはるかに小さい。

次数が最大dで直径がkのグラフの最大頂点数を とします。このとき、ムーア境界はどこになりますか。 ${\displaystyle n_{d,k}}$${\displaystyle n_{d,k}\leq M_{d,k}}$${\displaystyle M_{d,k}}$

${\displaystyle M_{d,k}={\begin{cases}1+d{\frac {(d-1)^{k}-1}{d-2}}&{\text{ if }}d>2\\2k+1&{\text{ if }}d=2\end{cases}}}$

この境界はごく少数のグラフで達成されるため、研究はムーアの境界にどれだけ近いグラフが存在するかに移ります。漸近的な動作については、次のことに注意してください。 ${\displaystyle M_{d,k}=d^{k}+O(d^{k-1})}$

パラメータ を定義します。すべてのkに対してであると推測されます。および であることが分かっています。 ${\displaystyle \mu_{k}=\liminf_{d\to\infty}{\frac{n_{d,k}}{d^{k}}}}$${\displaystyle \mu_{k}=1}$${\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1}$${\displaystyle \mu _{4}\geq 1/4}$

• ケージ（グラフ理論）
• 与えられた直径と最大次数を持つ既知の最大グラフの表
• 頂点対称次数直径有向グラフの表
• 最大次数と直径で制限された部分グラフ問題