次数直径問題

次数直径問題とは

次数直径問題は、グラフ理論の分野で注目されている課題の一つです。この問題では、最大次数がd、直径がkの条件を満たすグラフの中から、頂点数が最大のグラフGを見つけ出すことを目的としています。グラフGの頂点数については「ムーア・バウンド」という上限が設けられています。

ムーア・バウンドとは

ムーア・バウンドとは、特定の最大次数dと直径kに基づいて、グラフの最大頂点数を示すもので、数学的には次のように表現されます。

• - 最大頂点数をn_{d,k}とすると、n_{d,k}はムーア・バウンドM_{d,k}よりも小さい、すなわちn_{d,k} ≤ M_{d,k}が成り立ちます。

ムーア・バウンドM_{d,k}は次のように定義されており、dの値によって異なる計算式を持っています。

1. d > 2 の場合:

M_{d,k} = 1 + d rac{(d-1)^{k} - 1}{d-2}

2. d = 2 の場合:

M_{d,k} = 2k + 1

このムーア・バウンドに到達するグラフは非常に稀であることが知られており、特定の条件下での存在が示唆されています。特に、k=2でd=57の条件下では、ムーアバウンドに一致するグラフの存在が提案されましたが、まだ解決されていない問題でもあります。

ムーア・バウンドの性質

ムーア・バウンドM_{d,k}の漸近的な挙動について考えると、これは次のように近似されます。

M_{d,k} = d^{k} + O(d^{k-1})

この式によって、最大次数dや直径kが大きくなるにつれて、グラフの頂点数がどのように増加するかについての理解が深まります。さらに、任意のkに対して、以下のリミットが考察されます。

μ_k = lim inf_{d → ∞} rac{n_{d,k}}{d^{k}}

ここで、予想される結果は、μ_kが常に1であるというものです。この予想は他のkの値、たとえばμ_1, μ_2, μ_3, μ_5が1であることが既に知られているため、特に4に関してだけが未確認の状態です。

また、一般的にはμ_k ≥ 1.6^{k}となることが示されています。これにより、次数直径問題の基礎的な理解が得られます。

参考文献

今回の評価の参考にした資料として、以下の文献が挙げられます。これらの文献には、ムーアグラフや次数直径問題に関する重要な研究が含まれています。

• - Bannai, E.; Ito, T. (1973). 'On Moore graphs'. J. Fac. Sci. Univ. Tokyo Ser. A.
• - Hoffman, Alan J.; Singleton, Robert R. (1960). 'Moore graphs with diameter 2 and 3'. IBM Journal of Research and Development.
• - Singleton, Robert R. (1968). 'There is no irregular Moore graph'. American Mathematical Monthly.
• - Miller, Mirka; Širáň, Jozef (2005). 'Moore graphs and beyond: A survey of the degree/diameter problem'. Electronic Journal of Combinatorics.

このように、次数直径問題はグラフ理論における重要なテーマであり、さらなる研究が期待されています。

もう一度検索