強正則グラフ

Summarize Timeline Top Qs Fact Check

srg(v, k, λ, μ) の4つのパラメータは独立ではなく、以下の関係を満たしていなければならない：

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

この関係式は、数え上げ論法により非常に簡単に示すことができる。

1. グラフの全頂点を3つの階層に分ける。任意の頂点を1つ選んで、これは根（root）で、階層0にあるものとする。その k 個の近傍は階層1にあるとし、それ以外の全ての頂点は階層2にあるとする。
2. 階層1の頂点は根と直接つながっているので、根と共有する近傍が λ 個あることになり、これらは階層1にある。どの頂点の次数も k だから、階層1の頂点が持つ階層2の頂点との辺は、残った ${\displaystyle k-\lambda -1}$ 本である。よって階層1と階層2の間には合計 ${\displaystyle k\times (k-\lambda -1)}$ 本の辺がある。
3. 階層2の頂点は根と直接つながっていないので、根と共有する近傍が μ 個あることになり、これらは全て階層1になければいけない。階層2の頂点は ${\displaystyle (v-k-1)}$ 個で、どの頂点も階層1の頂点 μ 個とつながっている。よって階層1と階層2の間には合計 ${\displaystyle (v-k-1)\times \mu }$ 本の辺がある。
4. 階層1と階層2の間にある辺の本数を表す2つの表現を等しいと置けばよい。

I を単位行列、J を matrix of ones（英語版）（全成分が1の行列）で、いずれも v 次（行列）であるとする。強正則グラフの隣接行列 A は2つの方程式を満たさねばならない。まず、

${\displaystyle AJ=JA=kJ}$

これはグラフの正則性を述べなおした自明な関係である。これより、k は隣接行列の固有値で、全成分が1のベクトルがそれに対する固有ベクトルであることがわかる。

次は2次式の関係式で、グラフの強正則性を表す。

${\displaystyle {A}^{2}=k{I}+\lambda {A}+\mu ({J-I-A})}$

左辺の ij-成分は、頂点 i から頂点 j への長さ2の道の本数を表す。右辺の最初の項は頂点 i を自分自身と結ぶ、つまり k 本の「出」と「入り」の辺の数である。第2項は頂点 i と頂点 j が隣接しているときに、2辺でこれらを結ぶ道の本数を表す。第3項は頂点 i と頂点 j が隣接していないときの本数である。これら3つの場合は排他的で、かつ全てを尽くしているから、単純に和をとって等式が得られる。

逆に、グラフの隣接行列がこれら2条件を満たし、完全グラフでも空グラフでもないとき、強正則グラフである^[4]。

強正則グラフの隣接行列はちょうど3個の固有値を持つ：

• k は重複度1である（上述したもの）。
• ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}$ この重複度は ${\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$ である。
• ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}$ この重複度は ${\displaystyle {\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$ である。

重複度は整数でなければいけないから、これらの表現から v, k, μ, λ の間にはさらに制約が加わることになる。これはクレイン条件（Krein conditions）と呼ばれている。

${\displaystyle 2k+(v-1)(\lambda -\mu )=0}$ である強正則グラフは、対称カンファレンス行列（英語版）（conference matrix）との関連からカンファレンスグラフ（英語版）（conference graph）と呼ばれる。このときパラメータは

${\displaystyle {\text{srg}}\left(v,{\tfrac {1}{2}}(v-1),{\tfrac {1}{4}}(v-5),{\tfrac {1}{4}}(v-1)\right)}$

となる。${\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}$ である強正則グラフの隣接行列は、重複度の異なる整数固有値を持つことになる。

逆に、連結正則グラフは隣接行列の固有値が高々3個であるとき、強正則グラフである^[5]。

• 長さ5の閉路グラフ：srg(5, 2, 0, 1)
• ピーターセングラフ：srg(10, 3, 0, 1)
• クレブシュグラフ（英語版）（Clebsch graph）：srg(16, 5, 0, 2)
• シュリクハンデグラフ（英語版）（Shrikhande graph）は srg(16, 6, 2, 2) であり、距離推移グラフではない。
• n × n の正方ルークのグラフ（英語版）（rook's graph）、つまり両部が同じ頂点数からなる完全2部グラフ K_n,n の en:line graphであり、srg(n², 2n − 2, n − 2, 2) と表せる。n=4 のときはシュリクハンデグラフとパラメータが一致するが、これらはグラフ同型ではない。
• ホフマン–シングルトングラフ：srg(50, 7, 0, 1)
• ジェウィルスグラフ（英語版）（Gewirtz graph）：srg(56, 10, 0, 2)
• M22グラフ（英語版）：srg(77, 16, 0, 4)
• ヒグマン–シムスグラフ（英語版）（Higman–Sims graph）：srg(100, 22, 0, 6)
• バーレカンプ–ヴァン・リント–ザイデルグラフ（Berlekamp–van Lint–Seidel graph）：srg(243, 22, 1, 2)
• マクラフリングラフ（McLaughlin graph）：srg(275, 112, 30, 56)

強正則グラフは、自身とその補グラフがいずれも連結であるとき原始的（primitive）であると言う。ここに挙げた例は全て原始的である（さもなければ μ=0 または λ=k でなければならない）。

コンウェイの99グラフ問題はパラメータ srg(99, 14, 1, 2) のグラフが構成できるかを問う問題である。このようなグラフが存在するか否かは未解決であり、ジョン・ホートン・コンウェイはこの問題の賞金に1000ドルを提示した^[6]。

λ = 0 の強正則グラフはトライアングルフリー（英語版）（triangle free）である。頂点数が3未満の完全グラフと、全ての完全2部グラフ以外では、上に挙げた7つ（五角形、ピーターセングラフ、クレブシュグラフ、ホフマン–シングルトングラフ、ジェウィルスグラフ、M22グラフ、ヒグマン–シムスグラフ）が知られている全てである。

λ = 0 かつ μ = 1 の強正則グラフは内周5のムーアグラフになる。再び、上に挙げたグラフのうち3つ（五角形、ピーターセングラフ、ホフマン–シングルトングラフ）は、それぞれパラメータは (5, 2, 0, 1), (10, 3, 0, 1), (50, 7, 0, 1) で、知られているものはこれらで全てである。

ムーアグラフを作るパラメータとして残っている唯一の候補は (3250, 57, 0, 1) だが、これを満たすグラフが存在するかどうか、また存在すればそれは一意的かどうかは未解決である。

• Partial geometry（英語版）
• ザイデル隣接行列（英語版）
• Two-graph（英語版）