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