ムーアグラフ

グラフ理論においてムーアグラフとは、次数d、直径kの正則グラフで、頂点数が以下の上限に一致するものである。

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

直径k、内周2k+1のグラフで頂点数が最小のもの、とムーアグラフを定義することもできる。また内周が2k+1のときに長さgのサイクルをちょうど${\displaystyle {\frac {n}{g}}(m-n+1)}$個含むようなグラフと定義することもできる。ここでnは頂点数、mは辺の数である。実際、内周に一致するサイクルを上記の条件のように含むグラフが頂点数最小のグラフとなる (Azarija & Klavžar 2014)。

ムーアグラフという名前はエドワード・F・ムーア（英語版）にちなんで1960年にホフマンとシングルトンによって名付けられた。

次数と直径が与えられたとき最大の頂点数を持つものがムーアグラフであるが、これは次数と内周が与えられたときに最小の頂点数をもつグラフでもある。すなわちムーアグラフはケージ(Erdős, Rényi & Sós 1966)である。通常の定義ではムーアグラフの内周は必ず奇数になるが、ムーアグラフの頂点数、次数、直径の満たす関係式から出発して内周を偶数を許すように拡張することができる。そのような拡張されたムーアグラフはまたケージとなる。

次数と直径が与えられたとき頂点数の上限

次数3，直径2のムーアグラフ（ピーターセングラフ）。幅優先探索木においてi番目の階層の頂点数はd(d-1)ⁱになる。

Gを次数d、直径kの任意のグラフとする。頂点vをルートとして幅優先探索木を構成する。この木は0階層に1つの頂点（v自身）、1階層に高々d個の頂点がある。次の階層には高々d(d-1)個の頂点がある。というのは、2階層において、1階層目の頂点は0階層のvと隣接しているため2階層目と高々d-1の頂点と隣接する。同様の議論によって一般的に、i階層目（1 ≤ i ≤ k）には高々d(d-1)ⁱ 個の頂点が存在する。よって各階層の頂点数を足し上げると次式を得る。

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

ムーアグラフはホフマンとシングルトンによってこの上限に頂点数が一致するグラフとして定義された。ムーアグラフは次数d、直径kのグラフのうち頂点数が最大のものである。

その後、Singleton (1968) によって、ムーアグラフは直径k、内周2k+1を満たすグラフと同値であることが示された。直径と内周の条件によってグラフは正則となる。

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

ムーアグラフは最大次数と直径が与えられたときに最大頂点数のグラフとして定式化されるが、類似の議論によって最小次数と内周が与えられたときに最小頂点数のグラフとしても定式化されうる(Erdős, Rényi & Sós 1966).。Gを最小次数dと内周2k+1をもつ任意のグラフとしよう。任意の頂点vから始めて幅優先探索木を構成する。0階層にはちょうど1つのv自身が存在する。また1階層には少なくともd個の頂点が存在する。 2階層（k > 1）には, 少なくともd(d-1)個の頂点が存在する。なぜなら1階層の異なる2頂点は内周の制約から2階層に共通の近傍を持たないからだ。同様にして一般的に任意のi階層（1 ≤ i ≤ k）には少なくともd(d-1)ⁱ 個の頂点が存在する。よって各階層の頂点を足し上げれば頂点数の下限として次式を得る。

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

ムーアグラフのこの下限に頂点数が一致する。幅優先探索木においてある階層の異なる2頂点が下の階層で共通の近傍を持つとすると、内周の制約を破る短いサイクルが発生するため、任意のムーアグラフは内周は2k+1となる。よってムーアグラフは次数d、内周2k+1のグラフのうち頂点数が最小のもの、すなわちケージとなる。

偶数の内周2kについては、任意の一辺から幅優先探索木を構成することで同様の式を得る。最小次数がdでこの内周を満たすグラフの頂点数の下限は次式で与えられる。

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

ムーアグラフの定義を拡張して偶数内周を許した場合にも、そのようなグラフはケージとなる。

具体例

ホフマン-シングルトンの定理によれば、内周が5のムーアグラフの次数は2, 3, 7あるいは57のいずれかである。

• n > 2 の完全グラフ${\displaystyle K_{n}}$  (直径1, 内周3, 次数n-1, 頂点数n)

• 奇数頂点のサイクル ${\displaystyle C_{2n+1}}$. (直径n, 内周2n+1, 次数2, 頂点数2n+1)

• ピーターセングラフ(直径2, 内周5, 次数3, 頂点数10)

• ホフマンシングルトングラフ（直径2, 内周5, 次数7, 頂点数50)

• 直径2、内周5、次数57、頂点数3250のグラフが存在しうる。しかしいまだ構成されておらず、否定的な証明もされていない。

他の知られているムーアグラフと異なり、次数57のムーアグラフは頂点推移グラフとはならないことがHigmanによって証明されている。またMačajとŠiráňによれば、そのようなムーアグラフの自己同型群の位数は高々375である。

ムーアグラフの定義を内周が偶数も許容するように一般化すると、偶数内周のムーアグラフは一般化多角形の縮退したインシデントグラフに相当する。例えば、内周4の偶数サイクル ${\displaystyle C_{2n}}$, 完全二部グラフ ${\displaystyle K_{n,n}}$ や 次数3, 内周6のヒーウッドグラフ、次数3, 内周8のTutte–Coxeter graphがある。より一般に前出の例以外のムーアグラフの内周は5, 6, 8あるいは12でなくてはならない(Bannai & Ito 1973)(Damerell 1973) 。内周8のケージは一般n角形の存在定理であるFeit-Higmanの定理より従う。

参考文献

• Azarija, Jernej and Klavžar, Sandi「Moore graphs and cycles are extremal graphs for convex cycles」『Journal of Graph Theory』第80巻第1号、Wiley Online Library、2015年、34-42頁、doi:10.1002/jgt.21837。
• Bollobás, Béla (1998), "Chap.VIII.3", Modern graph theory, Graduate Texts in Mathematics 184, Springer-Verlag.
• Bannai, Eiichi and Ito, Tatsuro (Aug 1973). “On finite Moore graphs”. 東京大学理学部紀要. 第1類A, 数学 20 (2): 191-208. https://doi.org/10.15083/00039786. MR0323615
• Damerell, R. M. (1973), "On Moore graphs", Mathematical Proceedings of the Cambridge Philosophical Society 74: 227–236, doi:10.1017/S0305004100048015, MR0318004
• Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory", Studia Sci. Math. Hungar. 1: 215–235.
• Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, doi:10.1147/rd.45.0497, MR0140437
• Martin Mačaj; Jozef Širáň (2010). “Search for properties of the missing Moore graph”. Linear Algebra and its Applications (Elsevier) 432 (9): 2381-2398. doi:10.1016/j.laa.2009.07.018. https://doi.org/10.1016/j.laa.2009.07.018.
• Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly 75 (1): 42–43, doi:10.2307/2315106, MR0225679

関連項目

• 次数直径問題
  • Degree diameter problem（英語）
• Table of the largest known graphs of a given diameter and maximal degree（英語）

外部リンク

• Brouwer and Haemers: Spectra of graphs^{[リンク切れ]}
• Weisstein, Eric W., "Moore Graph", MathWorld.
• Weisstein, Eric W., "Hoffman-Singleton Theorem", MathWorld.