ケージ (グラフ理論)

グラフ理論において、ケージとは与えられた与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。

厳密に述べると次のようになる。(r,g)-グラフとは任意の頂点が相異なるr個の頂点と隣接し、かつグラフに含まれる最小のサイクルの長さがgに一致するものを指す。任意のr ≥ 2、g ≥ 3に対して(r,g)-グラフは存在することが知られている。(r,g)-ケージとは(r,g)-グラフのうちもっとも頂点数が少ないグラフのことである。

次数r、内周gのムーアグラフは存在すれば、ケージとなる。ムーアグラフの頂点数を表す式はケージに対して一般化することができる。すなわち奇内周gをもつグラフの頂点数は

1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}

以上となる。任意の(r,g)-グラフが上述の式を満たすと、定義からムーアグラフとなり、またケージとなる。同様に偶内周の場合は頂点数は

2\sum _{i=0}^{(g-2)/2}(r-1)^{i}

以上となる。また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)-ケージは頂点数2rの完全二部グラフK_r,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)-ケージの頂点数を次表にまとめる。ただし射影平面と一般化多角形によるものは除く。

r = 3:	4	6	10	14	24	30	58	70	112	126
g:	3	4	5	6	7	8	9	10	11	12
r = 4:	5	8	19	26	67	80				728
r = 5:	6	10	30	42		170				2730
r = 6:	7	12	40	62		312				7812
r = 7:	8	14	50	90

漸近的振る舞い

ムーアバウンドの議論から、大きいgに対して頂点数はgの指数関数的に増大する項で下から抑えられる。言い換えると、gはnの対数に比例する項で上から抑えられる。すなわち次式を得る。

g\leq 2\log _{r-1}n+O(1).

実際この上限に近づくと予想されている(Bollobás & Szemerédi 2002)。知られている中でもっともよいgの下限は比較的小さな定数係数の対数で書けている。とくにラマヌジャングラフ(Lubotzky, Phillips & Sarnak 1988) は次式を満たす。

g\geq {\frac {4}{3}}\log _{r-1}n+O(1).

これらのグラフがケージとなることはおそらくないが、これらのグラフの存在によって上限のグラフはケージとなる必要がある。

参考文献

Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge Mathematical Library, pp. 180–190, ISBN 0-521-45897-8 .
Bollobás, Béla; Szemerédi, Endre (2002), “Girth of sparse graphs”, Journal of Graph Theory 39 (3): 194–200, doi:10.1002/jgt.10023, MR1883596 .
Exoo, G; Jajcay, R (2008), “Dynamic Cage Survey”, Electronic Journal of Combinatorics (Dynamic Survey) DS16 .
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 .
Hartsfield, Nora; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, pp. 77–81, ISBN 0-12-328552-6 .
Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, pp. 183–213, ISBN 0-521-43594-3 .
Lubotzky, A.; Phillips, R.; Sarnak, P. (1988), “Ramanujan graphs”, Combinatorica 8 (3): 261–277, doi:10.1007/BF02126799, MR963118 .
Tutte, W. T. (1947), “A family of cubical graphs”, Proc. Cambridge Philos. Soc. 43 (4): 459–474, doi:10.1017/S0305004100023720 .

外部リンク

Brouwer, Andries E. Cages
Royle, Gordon. Cubic Cages and Higher valency cages
Weisstein, Eric W. "Cage Graph". mathworld.wolfram.com (英語).