強正則グラフ

グラフ理論において強正則グラフ（きょうせいそくグラフ、英: strongly regular graph）は次のように定義される。頂点数 v、次数 k の正則グラフ G = (V, E) が強正則であるとは、整数 λ と μ が存在して、

任意の隣接する2頂点は、ちょうど λ 個の近傍を共有する。
任意の隣接しない2頂点は、ちょうど μ 個の近傍を共有する。

の2条件を満たすことを言う。このようなグラフは srg(v, k, λ, μ) と表されることがある。強正則グラフはラジ・チャンドラ・ボース（英語版）によって1963年に導入された^[1]。

著者によっては、条件を自明に満たすグラフ、つまり、完全グラフおよび頂点数が同一の複数の完全グラフの非交和から成るグラフ^[2]^[3]と、それらの補グラフ（同一個数の独立集合の集まりからできる完全多部グラフ（英語版））を強正則グラフに含めないこともある。

強正則グラフ srg(v, k, λ, μ) の補グラフはまた強正則グラフ、srg(v, v−k−1, v−2−2k+μ, v−2k+λ) になる。

強正則グラフは μ が0でないとき、直径2の距離正則グラフ（英語版）（distance-regular graph）である。強正則グラフは λ が1であるとき、局所線形グラフ（英語版）（locally linear graph）である。

性質

パラメータ間の関係

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

(v-k-1)\mu =k(k-\lambda -1)

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

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

隣接行列

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

AJ=JA=kJ

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

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

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

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

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

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

となる。 $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) だが、これを満たすグラフが存在するかどうか、また存在すればそれは一意的かどうかは未解決である。

注釈・出典

^ https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math 13 (1963) 389–419. (p. 122)
^ Brouwer, Andries E; Haemers, Willem H. Spectra of Graphs. p. 101 Archived 2012-03-16 at the Wayback Machine.
^ Godsil & Royle 2001, p. 218.
^ Cameron, P.J.; van Lint, J.H. (1991), Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, p. 37, ISBN 978-0-521-42385-4
^ Godsil & Royle 2001, p. 220, Lemma 10.2.1.
^ Conway, John H., Five $1,000 Problems (Update 2017), Online Encyclopedia of Integer Sequences, https://oeis.org/A248380/a248380.pdf 2019年2月12日閲覧。

参考文献

A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
Godsil, C.; Royle, G. (2001). Algebraic Graph Theory. Springer-Verlag. ISBN 0-387-95241-1. Zbl 0968.05002. https://books.google.co.jp/books?id=GeSPBAAAQBAJ