right|thumb|The Tutte (3,8)-cage. グラフ理論において、ケージとは与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。
厳密に述べると次のようになる。(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の完全グラフKr+1となる。また(r,4)-ケージは頂点数2rの完全二部グラフKr,rとなる。
他の特筆すべきケージ（ムーアグラフを含む。）: (3,5)-ケージ: ピーターセングラフ、頂点数10 (3,6)-ケージ: ヒーウッドグラフ、頂点数14 (3,7)-ケージ: マギーグラフ、頂点数24 (3,8)-ケージ: Tutte–Coxeter graph、頂点数30 (3,10)-ケージ: バラバン10-ケージ、頂点数70 (4,5)-ケージ: ロバートソングラフ、頂点数19 (7,5)-ケージ: ホフマン-シングルトングラフ、頂点数50 r-1が素数のべき乗のとき、(r,6)-ケージは射影平面のインシデント・グラフとなる。 r-1が素数のべき乗のとき、(r,8)-ケージと(r,12)-ケージは一般化多角形となる。
r > 2かつg > 2の場合に知られている(r,g)-ケージの頂点数を次表にまとめる。ただし射影平面と一般化多角形によるものは除く。 g: 3 4 5 6 7 8 9 10 11 12 r = 3: 4 6 10 14 24 30 58 70 112 126 r = 4: 5 8 19 26 67 80728 r = 5: 6 10 30 42 1702730 r = 6: 7 12 40 62 3127812 r = 7: 8 14 50 90
漸近的振る舞い ムーアバウンドの議論から、大きいgに対して頂点数はgの指数関数的に増大する項で下から抑えられる。言い換えると、gはnの対数に比例する項で上から抑えられる。すなわち次式を得る。
実際この上限に近づくと予想されている。知られている中でもっともよいgの下限は比較的小さな定数係数の対数で書けている。とくにラマヌジャングラフ は次式を満たす。
これらのグラフがケージとなることはおそらくないが、これらのグラフの存在によって上限のグラフはケージとなる必要がある。
参考文献 . . . . . . . .
外部リンク Brouwer, Andries E. Cages Royle, Gordon. Cubic Cages and Higher valency cages