ムーアグラフ

ムーアグラフの概要

ムーアグラフは、グラフ理論における重要な概念であり、特に正則性や直径に関する研究で注目されています。このグラフは、次数dおよび直径kを持つ正則グラフであり、特定の条件を満たすものと定義されます。損得高い条件を示す式は、以下のようになります。

${1+d\sum _{i=0}^{k-1}(d-1)^{i}}$

この式において、dはグラフの次数を、kは直径を表します。

ムーアグラフの特性

ムーアグラフは、同時に内周が$2k+1$であるという条件とも関係しています。また、長さgのサイクルをちょうど${\frac {n}{g}}(m-n+1)$個含むようなグラフとしても定義されます。ここで、nは頂点の数、mは辺の数です。特に、内周が$2k+1$に一致するサイクルを含むグラフが、与えられた条件を満たす場合、それが頂点数の最小のグラフであることが分かっています。

ムーアグラフの名前は、1960年にホフマンとシングルトンによってエドワード・F・ムーアにちなんで名付けられました。ムーアグラフは、次数dおよび直径kが与えられた際に持つ頂点数の最大値を評価するための重要な手段となります。同時に、同様の条件を考慮することで、最小の頂点数を持つグラフも特定でき、これをケージと呼びます。実際には、通常の定義において、ムーアグラフは内周が必ず奇数である必要がありますが、この定義を拡張することで偶数内周も許容できるようになります。

ムーアグラフの生成過程

具体的には、ある任意のグラフGにおいて、次数d、直径kが指定される場合を考えます。幅優先探索を用いることで、ルートvから形成される木を作成します。この木の0階層には1つの頂点（v自身）があり、1階層には高々d個、2階層には高々d(d-1)個の頂点が存在することが示されます。一般的に考えると、i階層には高々d(d-1)^i個の頂点があるため、これを全て足し合わせることでグラフの頂点数の上限が得られます。

この性質はムーアグラフを考える上で非常に重要です。なぜなら、グラフの構造がどのように形成されるかを理解する上で助けになり、グラフの特定の属性を特定する助けともなります。

ケージとしてのムーアグラフ

ムーアグラフは、最大次数や直径が与えられた場合に頂点数が最大なることが云々される一方、最小次数および内周で最小の頂点数を有することも問題となります。このような観点から、ムーアグラフは多くの研究において興味深い題材となっています。さらに、グラフ内の各階層における頂点数を基に、内周が指定される場合の最小限度も評価されています。

例えば、$d$が最低限の次数で、内周が$2k+1$であるようなグラフGについて考えた場合、同様に幅優先探索の手法を使うと、各階層における頂点数を評価できます。これにより、ムーアグラフの定義を基にした様々な条件を明確化でき、特定のグラフプロパティに対する理解を深めることができます。

具体例と展望

ムーアグラフに関する研究は非常に多岐にわたりますが、特にホフマン-シングルトン定理は内周が5のムーアグラフが持つ可能性のある次数について示唆を与えています。ここでは、完全グラフや奇数頂点のサイクル、特定の次数と内周を持つグラフの具体例が挙げられています。また、次数57のムーアグラフが存在しうる可能性やその性質についても研究が続けられています。「偶数内周のムーアグラフ」については、より広範囲な応用可能性があることが示されています。

まとめると、ムーアグラフはグラフ理論における重要な構造であり、さまざまな条件を持つグラフに関する知見を提供します。これにより、理論的な解析や具体的な応用への理解を深め、さらなる研究の基盤となることでしょう。

もう一度検索