ケージ (グラフ理論)のソースを表示

[[ファイル:Tutte_eight_cage.svg|right|thumb|The Tutte (3,8)-cage.]]
[[グラフ理論]]において、'''ケージ'''とは与えられた与えられた[[内周 (グラフ理論)|内周]]を満たす[[正則グラフ]]のうち、頂点数が最小のものである。

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

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

:<math>1+r\sum_{i=0}^{(g-3)/2}(r-1)^i</math>

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

:<math>2\sum_{i=0}^{(g-2)/2}(r-1)^i</math>

以上となる。また''r''と''g''の組み合わせによっては複数の同型でないケージが存在しうる。例えば、頂点数70となる(3,10)-ケージは[[バラバン10-ケージ]]、[[Harries graph]]と[[Harries-Wong graph]]の同型でない三つが存在する。一方で (3,11)-ケージは頂点数が112となる[[バラバン11-ケージ]]のみである。

== 具体例 ==
次数1のグラフはサイクルを持たない。次数2のグラフはサイクルそのもので内周は頂点数に一致する。そのため''r'' ≥ 3の場合についてケージを考える。(''r'',3)-ケージは頂点数r+1の[[完全グラフ]]''K''<sub>''r''+1</sub>となる。また(''r'',4)-ケージは頂点数2''r''の[[完全二部グラフ]]''K''<sub>''r'',''r''</sub>となる。

他の特筆すべきケージ（ムーアグラフを含む。）:
* (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'')-ケージの頂点数を次表にまとめる。ただし射影平面と一般化多角形によるものは除く。
{| class="wikitable" style="margin-bottom: 10px;"
|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
! 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''の対数に比例する項で上から抑えられる。すなわち次式を得る。

:<math>g\le 2\log_{r-1} n + O(1).</math>

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

:<math>g\ge \frac{4}{3}\log_{r-1} n + O(1).</math>

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

== 参考文献 ==
* {{Citation|last = Biggs|first = Norman|edition = 2nd|isbn = 0-521-45897-8|pages = 180–190|publisher = Cambridge Mathematical Library|title = Algebraic Graph Theory|year = 1993}}.
* {{Citation|last1 = Bollobás|first1 = Béla|last2 = Szemerédi|first2 = Endre|doi = 10.1002/jgt.10023|issue = 3|journal = Journal of Graph Theory|mr = 1883596|pages = 194–200|title = Girth of sparse graphs|volume = 39|year = 2002}}.
* {{Citation|last1 = Exoo|first1 = G|last2 = Jajcay|first2 = R|journal = [[Electronic Journal of Combinatorics|Electronic Journal of Combinatorics (Dynamic Survey)]]|title = Dynamic Cage Survey|url = http://www.combinatorics.org/ojs/index.php/eljc/article/download/ds16/pdf|volume = DS16|year = 2008}}.
* {{Citation|last1 = Erdős|first1 = Paul|author1-link = Paul Erdős|last2 = Rényi|first2 = Alfréd|author2-link = Alfréd Rényi|last3 = Sós|first3 = Vera T.|author3-link = Vera T. Sós|journal = Studia Sci. Math. Hungar.|pages = 215–235|title = On a problem of graph theory|url = http://www.math-inst.hu/~p_erdos/1966-06.pdf|volume = 1|year = 1966}}.
* {{Citation|last1 = Hartsfield|first1 = Nora|author1-link = Nora Hartsfield|last2 = Ringel|first2 = Gerhard|author2-link = Gerhard Ringel|isbn = 0-12-328552-6|pages = 77–81|publisher = Academic Press|title = Pearls in Graph Theory: A Comprehensive Introduction|year = 1990}}.
* {{Citation|last1 = Holton|first1 = D. A.|last2 = Sheehan|first2 = J.|isbn = 0-521-43594-3|pages = 183–213|publisher = [[Cambridge University Press]]|title = The Petersen Graph|year = 1993}}.
* {{Citation|last1 = Lubotzky|first1 = A.|last2 = Phillips|first2 = R.|last3 = Sarnak|first3 = P.|doi = 10.1007/BF02126799|issue = 3|journal = [[Combinatorica]]|mr = 963118|pages = 261–277|title = Ramanujan graphs|volume = 8|year = 1988}}.
* {{Citation|last = Tutte|first = W. T.|author-link = William Thomas Tutte|doi = 10.1017/S0305004100023720|issue = 4|journal = Proc. Cambridge Philos. Soc.|pages = 459–474|title = A family of cubical graphs|volume = 43|year = 1947}}.

== 外部リンク ==
* Brouwer, Andries E. [http://www.win.tue.nl/~aeb/drg/graphs/cages/cages.html Cages]
* Royle, Gordon. [http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/index.html Cubic Cages] and [http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/allcages.html Higher valency cages]
* {{MathWorld|title = Cage Graph|urlname = CageGraph}}

{{デフォルトソート:けえし}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]