ケージ (グラフ理論)

グラフ理論において、ケージとは与えられた与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。
厳密に述べると次のようになる。("r","g")-グラフとは任意の頂点が相異なる"r"個の頂点と隣接し、かつグラフに含まれる最小のサイクルの長さが"g"に一致するものを指す。任意の"r" ≥ 2、"g" ≥ 3に対して(r,g)-グラフは存在することが知られている。("r","g")-ケージとは("r","g")-グラフのうちもっとも頂点数が少ないグラフのことである。
次数"r"、内周gのムーアグラフは存在すれば、ケージとなる。ムーアグラフの頂点数を表す式はケージに対して一般化することができる。すなわち奇内周gをもつグラフの頂点数は
以上となる。任意の(r,g)-グラフが上述の式を満たすと、定義からムーアグラフとなり、またケージとなる。同様に偶内周の場合は頂点数は
以上となる。また"r"と"g"の組み合わせによっては複数の同型でないケージが存在しうる。例えば、頂点数70となる(3,10)-ケージはバラバン10-ケージ、Harries graphとHarries-Wong graphの同型でない三つが存在する。一方で (3,11)-ケージは頂点数が112となるバラバン11-ケージのみである。
具体例.
次数1のグラフはサイクルを持たない。次数2のグラフはサイクルそのもので内周は頂点数に一致する。そのため"r" ≥ 3の場合についてケージを考える。("r",3)-ケージは頂点数r+1の完全グラフ"K""r"+1となる。また("r",4)-ケージは頂点数2"r"の完全二部グラフ"K""r","r"となる。
他の特筆すべきケージ（ムーアグラフを含む。）:
"r" > 2かつ"g" > 2の場合に知られている("r","g")-ケージの頂点数を次表にまとめる。ただし射影平面と一般化多角形によるものは除く。
漸近的振る舞い.
ムーアバウンドの議論から、大きい"g"に対して頂点数は"g"の指数関数的に増大する項で下から抑えられる。言い換えると、"g"は"n"の対数に比例する項で上から抑えられる。すなわち次式を得る。
実際この上限に近づくと予想されている。知られている中でもっともよいgの下限は比較的小さな定数係数の対数で書けている。とくにラマヌジャングラフ は次式を満たす。
これらのグラフがケージとなることはおそらくないが、これらのグラフの存在によって上限のグラフはケージとなる必要がある。