ケージ（グラフ理論）

数学のグラフ理論の分野において、ケージとは、その周囲長に対して可能な限り少ない頂点を持つ正則グラフのことである。

正式には、( r , g )グラフは、各頂点がちょうどr 個の隣接頂点を持ち、最短閉路の長さがちょうどgであるグラフとして定義されます。( r , g )ケージは、すべての( r , g )グラフの中で、頂点の数が可能な限り少ない( r , g )グラフです。(3, g )ケージは、しばしばgケージと呼ばれます。

r ≥ 2とg ≥ 3の任意の組み合わせに対して( r , g )グラフが存在することが知られています。したがって、すべての( r , g )ケージが存在することになります。

次数r、内周gのムーアグラフが存在する場合、それはケージでなければならない。さらに、ムーアグラフのサイズの上限はケージにも一般化できる。つまり、内周gが奇数であるケージは、少なくとも

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

頂点は、偶数円周gのケージは少なくとも

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

頂点。ちょうどこれだけの頂点を持つ( r , g )グラフは、定義によりムーアグラフであり、したがって自動的にケージになります。

rとgの特定の組み合わせに対して、複数のケージが存在する場合があります。たとえば、それぞれ 70 個の頂点を持つ 3 つの非同型 (3, 10)ケージがあります。バラバン 10 ケージ、ハリーズ グラフ、ハリーズ–ウォン グラフです。しかし、 (3, 11)ケージは1 つだけです。バラバン 11 ケージ(112 個の頂点を持つ) です。

1-正則グラフにはサイクルがなく、連結された2-正則グラフの内周は頂点の数に等しいため、ケージはr ≥ 3 の場合にのみ重要です。( r ,3)-ケージはr + 1 頂点の完全グラフ K _{r  + 1}であり 、( r ,4)-ケージは2 r頂点の完全二部グラフK _{r , r}です。

注目すべきケージには以下のものがあります:

• (3,5)-ケージ:ピーターセングラフ、10頂点
• (3,6)-ケージ:ヒーウッドグラフ、14頂点
• (3,7)-ケージ:マギーグラフ、24頂点
• (3,8)-ケージ: Tutte-Coxeterグラフ、30頂点
• (3,10)-ケージ:バラバン10-ケージ、70頂点
• (3,11)-ケージ:バラバン11-ケージ、112頂点
• (4,5)-ケージ:ロバートソングラフ、19頂点
• (7,5)-ケージ:ホフマン-シングルトングラフ、頂点数50。
• r  − 1 が素数冪のとき、( r ,6)ケージは射影平面の接続グラフです。
• r  − 1が素数べき乗のとき、( r ,8)ケージと( r ,12)ケージは一般化された多角形です。

射影平面と一般化多角形以外の、 r > 2 およびg > 2 の値に対する既知の ( r , g ) ケージ内の頂点の数は次のとおりです。

gの値が大きい場合、ムーアの限界は、頂点の数n がgの関数として少なくとも1 指数関数的に増加する必要があることを意味します。同様に、g は最大でもnの対数に比例します。より正確には、

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

この境界は厳密であるか、それに近いと考えられている (Bollobás & Szemerédi 2002)。g の最もよく知られている下限も対数的であるが、定数係数はより小さい (つまりn は単指数的に増加するが、ムーアの境界よりも高い割合で増加する)。具体的には、Lubotzky、Phillips、Sarnak (1988) によって定義されたラマヌジャングラフの構成は、次の境界を満たす 。

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

この境界は、Lazebnik、Ustimenko、Woldar (1995) によってわずかに改良されました。

これらのグラフ自体がケージである可能性は低いですが、その存在により、ケージに必要な頂点の数に上限が与えられます。

• ビッグス、ノーマン（1993）、代数的グラフ理論（第2版）、ケンブリッジ数学図書館、pp. 180-190、ISBN 0-521-45897-8。
• Bollobás, ベラ州; Szemerédi、Endre (2002)、「Girth of sparsegraphs」、Journal of Graph Theory、39 (3): 194–200、doi : 10.1002/jgt.10023、MR  1883596。
• Exoo, G; Jajcay, R (2008)、「Dynamic Cage Survey」、Dynamic Surveys、Electronic Journal of Combinatorics、DS16、2015-01-01にオリジナルからアーカイブ、 2012-03-25に取得。
• ポール・エルデシュ; Rényi, アルフレッド; Sós、Vera T. (1966)、「グラフ理論の問題について」(PDF)、Studia Sci.数学。ハンガル。、1 : 215–235、オリジナル(PDF)から2016 年 3 月 9 日にアーカイブ、2010 年 2 月 23 日に取得。
• ハーツフィールド、ノラ、リンゲル、ゲルハルト（1990）、グラフ理論の真珠：包括的入門、アカデミックプレス、pp. 77-81、ISBN 0-12-328552-6。
• ホルトン, DA; シーハン, J. (1993)、『ピーターセングラフ』、ケンブリッジ大学出版局、pp. 183–213、ISBN 0-521-43594-3。
• Lazebnik, F.; Ustimenko, VA; Woldar, AJ (1995)、「高内周の密グラフの新シリーズ」、米国数学会報、新シリーズ、32 (1): 73–79、arXiv : math/9501231、doi :10.1090/S0273-0979-1995-00569-0、MR  1284775。
• Lubotzky, A. ; Phillips, R.; Sarnak, P. (1988)、「ラマヌジャングラフ」、Combinatorica、8 (3): 261–277、doi :10.1007/BF02126799、MR  0963118。
• Tutte, WT (1947)、「立方体グラフのファミリー」、Proc. Cambridge Philos. Soc.、43 (4): 459–474、Bibcode :1947PCPS...43..459T、doi :10.1017/S0305004100023720。

• ブラウワー、アンドリース・E・ケージス
• ロイル、ゴードン。立方ケージと高原子価ケージ
• ワイスタイン、エリック・W.「ケージグラフ」。マスワールド。