ケージ (グラフ理論)

グラフ理論におけるケージについての詳解

グラフ理論におけるケージは、与えられた内周条件を満たす正則グラフの中で、頂点数が最も少ないものを指します。具体的には、(r,g)-グラフは、任意の頂点が相異なるr個の頂点と隣接し、最小のサイクルの長さがgであるようなグラフです。ここで、rは頂点の次数を、gは内周の長さを表します。この定義に従い、任意のr（r≥2）およびg（g≥3）に対する(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の組み合わせによって、同型でない複数のケージが存在する場合があることです。たとえば、(3,10)-ケージの場合、頂点数70のバラバン10-ケージとHarriesグラフおよびHarries-Wongグラフが同型でないことが知られています。一方、(3,11)-ケージは、頂点数112のバラバン11-ケージのみが存在します。

具体例を挙げると、次数1のグラフはサイクルを持たず、次数2のグラフは単なるサイクルで内周はその頂点数に一致します。従って、r≥3のケースに注目すると、(r,3)-ケージは完全グラフK_{r+1}、(r,4)-ケージは完全二部グラフK_{r,r}となります。

さらに、特筆すべきケージの例として、次のようなものがあります：

• - (3,5)-ケージ：ピーターセングラフ、頂点数10
• - (3,6)-ケージ：ヒーウッドグラフ、頂点数14
• - (3,7)-ケージ：マギーグラフ、頂点数24
• - (3,8)-ケージ：Tutte–Coxeterグラフ、頂点数30
• - (4,5)-ケージ：ロバートソングラフ、頂点数19
• - (7,5)-ケージ：ホフマン-シングルトングラフ、頂点数50

特に、r-1が素数のべき乗のとき、(r,6)-ケージは射影平面のインシデント・グラフとして、(r,8)-ケージや(r,12)-ケージは一般化多角形として構成されることがあります。

次に、知られている(r,g)-ケージの頂点数に関して、r>2かつg>2の場合のものを表にまとめることができますが、ここでは射影平面や一般化多角形による影響は除いています。

漸近的振る舞い

ムーアの境界に基づく分析により、大きなgに対しては頂点数がgの指数関数的に増大することが分かります。これは、gがnの対数に比例する形で上から抑えられることを示しています。これに基づいて次の不等式が得られます。

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

この上限に近づくとされている研究結果があります。また、これらのグラフの最良の下限としては、比較的小さな定数係数の対数の形で表せるとされています。

特にラマヌジャンラフは次の条件を満たしています。

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

ただし、これらのグラフがケージとなることは可能性が低いとされていますが、上限に近いグラフはケージである必要があると考えられています。

このように、ケージはグラフ理論における重要なテーマであり、その存在と性質は様々な数学的および応用的問題に影響を与えています。

もう一度検索