強正則グラフ

グラフ理論において強正則グラフ（きょうせいそくグラフ、）は次のように定義される。頂点数 "v"、次数 "k" の正則グラフ "G" = ("V", "E") が強正則であるとは、整数 λ と μ が存在して、
の2条件を満たすことを言う。このようなグラフは srg("v", "k", λ, μ) と表されることがある。強正則グラフはによって1963年に導入された。
著者によっては、条件を自明に満たすグラフ、つまり、完全グラフおよび頂点数が同一の複数の完全グラフの非交和から成るグラフと、それらの補グラフ（同一個数の独立集合の集まりからできる完全）を強正則グラフに含めないこともある。
強正則グラフ srg("v", "k", λ, μ) の補グラフはまた強正則グラフ、srg("v", "v−k"−1, "v"−2−2"k"+μ, "v"−2"k"+λ) になる。
強正則グラフは μ が0でないとき、直径2の（distance-regular graph）である。強正則グラフは λ が1であるとき、（locally linear graph）である。
性質.
パラメータ間の関係.
srg("v", "k", λ, μ) の4つのパラメータは独立ではなく、以下の関係を満たしていなければならない：
この関係式は、数え上げ論法により非常に簡単に示すことができる。
隣接行列.
"I" を単位行列、"J" を （全成分が1の行列）で、いずれも "v" 次（行列）であるとする。強正則グラフの隣接行列 "A" は2つの方程式を満たさねばならない。まず、
これはグラフの正則性を述べなおした自明な関係である。これより、"k" は隣接行列の固有値で、全成分が1のベクトルがそれに対する固有ベクトルであることがわかる。
次は2次式の関係式で、グラフの強正則性を表す。
左辺の "ij"-成分は、頂点 "i" から頂点 "j" への長さ2の道の本数を表す。右辺の最初の項は頂点 "i" を自分自身と結ぶ、つまり "k" 本の「出」と「入り」の辺の数である。第2項は頂点 "i" と頂点 "j" が隣接しているときに、2辺でこれらを結ぶ道の本数を表す。第3項は頂点 "i" と頂点 "j" が隣接していないときの本数である。これら3つの場合は排他的で、かつ全てを尽くしているから、単純に和をとって等式が得られる。
逆に、グラフの隣接行列がこれら2条件を満たし、完全グラフでも空グラフでもないとき、強正則グラフである。
固有値.
強正則グラフの隣接行列はちょうど3個の固有値を持つ：
重複度は整数でなければいけないから、これらの表現から "v", "k", "μ", "λ" の間にはさらに制約が加わることになる。これはクレイン条件（Krein conditions）と呼ばれている。
formula_12 である強正則グラフは、対称（conference matrix）との関連から（conference graph）と呼ばれる。このときパラメータは
となる。formula_14 である強正則グラフの隣接行列は、重複度の異なる整数固有値を持つことになる。
逆に、連結正則グラフは隣接行列の固有値が高々3個であるとき、強正則グラフである。
例.
強正則グラフは、自身とその補グラフがいずれも連結であるとき原始的（primitive）であると言う。ここに挙げた例は全て原始的である（さもなければ μ=0 または λ=k でなければならない）。
コンウェイの99グラフ問題はパラメータ srg(99, 14, 1, 2) のグラフが構成できるかを問う問題である。このようなグラフが存在するか否かは未解決であり、ジョン・ホートン・コンウェイはこの問題の賞金に1000ドルを提示した。
ムーアグラフ.
λ = 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) だが、これを満たすグラフが存在するかどうか、また存在すればそれは一意的かどうかは未解決である。