頂点数13のペイリーグラフ (英語版 ) は、パラメータ srg(13,6,2,3) の強正則グラフである。
グラフ理論 において強正則グラフ (きょうせいそくグラフ、英 : strongly regular graph )は次のように定義される。頂点数 v 、次数 k の正則グラフ G = (V , E ) が強正則 であるとは、整数 λ と μ が存在して、
任意の隣接する2頂点は、ちょうど λ 個の近傍を共有する。
任意の隣接しない2頂点は、ちょうど μ 個の近傍を共有する。
の2条件を満たすことを言う。このようなグラフは srg(v , k , λ, μ) と表されることがある。強正則グラフはラジ・チャンドラ・ボース (英語版 ) によって1963年に導入された[ 1] 。
著者によっては、条件を自明に満たすグラフ、つまり、完全グラフ および頂点数が同一の複数の完全グラフの非交和から成るグラフ[ 2] と、それらの補グラフ (同一個数の独立集合の集まりからできる完全多部グラフ (英語版 ) )を強正則グラフに含めないこともある。
強正則グラフ 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
)
μ
=
k
(
k
−
λ
−
1
)
{\displaystyle (v-k-1)\mu =k(k-\lambda -1)}
この関係式は、数え上げ論法により非常に簡単に示すことができる。
グラフの全頂点を3つの階層に分ける。任意の頂点を1つ選んで、これは根(root)で、階層0にあるものとする。その k 個の近傍は階層1にあるとし、それ以外の全ての頂点は階層2にあるとする。
階層1の頂点は根と直接つながっているので、根と共有する近傍が λ 個あることになり、これらは階層1にある。どの頂点の次数も k だから、階層1の頂点が持つ階層2の頂点との辺は、残った
k
−
λ
−
1
{\displaystyle k-\lambda -1}
本である。よって階層1と階層2の間には合計
k
×
(
k
−
λ
−
1
)
{\displaystyle k\times (k-\lambda -1)}
本の辺がある。
階層2の頂点は根と直接つながっていないので、根と共有する近傍が μ 個あることになり、これらは全て階層1になければいけない。階層2の頂点は
(
v
−
k
−
1
)
{\displaystyle (v-k-1)}
個で、どの頂点も階層1の頂点 μ 個とつながっている。よって階層1と階層2の間には合計
(
v
−
k
−
1
)
×
μ
{\displaystyle (v-k-1)\times \mu }
本の辺がある。
階層1と階層2の間にある辺の本数を表す2つの表現を等しいと置けばよい。
I を単位行列 、J を matrix of ones (英語版 ) (全成分が1の行列)で、いずれも v 次(行列)であるとする。強正則グラフの隣接行列 A は2つの方程式を満たさねばならない。まず、
A
J
=
J
A
=
k
J
{\displaystyle AJ=JA=kJ}
これはグラフの正則性を述べなおした自明な関係である。これより、k は隣接行列の固有値で、全成分が1のベクトルがそれに対する固有ベクトルであることがわかる。
次は2次式の関係式で、グラフの強正則性を表す。
A
2
=
k
I
+
λ
A
+
μ
(
J
−
I
−
A
)
{\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である(上述したもの)。
1
2
[
(
λ
−
μ
)
+
(
λ
−
μ
)
2
+
4
(
k
−
μ
)
]
,
{\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}
この重複度は
1
2
[
(
v
−
1
)
−
2
k
+
(
v
−
1
)
(
λ
−
μ
)
(
λ
−
μ
)
2
+
4
(
k
−
μ
)
]
{\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}
である。
1
2
[
(
λ
−
μ
)
−
(
λ
−
μ
)
2
+
4
(
k
−
μ
)
]
,
{\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}
この重複度は
1
2
[
(
v
−
1
)
+
2
k
+
(
v
−
1
)
(
λ
−
μ
)
(
λ
−
μ
)
2
+
4
(
k
−
μ
)
]
{\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)と呼ばれている。
2
k
+
(
v
−
1
)
(
λ
−
μ
)
=
0
{\displaystyle 2k+(v-1)(\lambda -\mu )=0}
である強正則グラフは、対称カンファレンス行列 (英語版 ) (conference matrix)との関連からカンファレンスグラフ (英語版 ) (conference graph)と呼ばれる。このときパラメータは
srg
(
v
,
1
2
(
v
−
1
)
,
1
4
(
v
−
5
)
,
1
4
(
v
−
1
)
)
{\displaystyle {\text{srg}}\left(v,{\tfrac {1}{2}}(v-1),{\tfrac {1}{4}}(v-5),{\tfrac {1}{4}}(v-1)\right)}
となる。
2
k
+
(
v
−
1
)
(
λ
−
μ
)
≠
0
{\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}
である強正則グラフの隣接行列は、重複度の異なる整数固有値を持つことになる。
逆に、連結正則グラフは隣接行列の固有値が高々3個であるとき、強正則グラフである。
長さ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部グラフ Kn,n の en:line graph であり、srg(n 2 , 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 .
^ 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
^ Conway, John H. , Five $1,000 Problems (Update 2017) , Online Encyclopedia of Integer Sequences, https://oeis.org/A248380/a248380.pdf 2019年2月12日 閲覧。