ムーアグラフ

グラフ理論においてムーアグラフとは、次数d、直径kの正則グラフで、頂点数が以下の上限に一致するものである。 直径k、内周2k+1のグラフで頂点数が最小のもの、とムーアグラフを定義することもできる。また内周が2k+1のときに長さgのサイクルをちょうど個含むようなグラフと定義することもできる。ここでnは頂点数、mは辺の数である。実際、内周に一致するサイクルを上記の条件のように含むグラフが頂点数最小のグラフとなる。 ムーアグラフという名前はにちなんで1960年にホフマンとシングルトンによって名付けられた。 次数と直径が与えられたとき最大の頂点数を持つものがムーアグラフであるが、これは次数と内周が与えられたときに最小の頂点数をもつグラフでもある。すなわちムーアグラフはケージである。通常の定義ではムーアグラフの内周は必ず奇数になるが、ムーアグラフの頂点数、次数、直径の満たす関係式から出発して内周を偶数を許すように拡張することができる。そのような拡張されたムーアグラフはまたケージとなる。