強正則グラフ

グラフ理論において強正則グラフ（きょうせいそくグラフ、英: strongly regular graph）は次のように定義される。頂点数 v、次数 k の正則グラフ G = (V, E) が強正則であるとは、整数 λ と μ が存在して、 * 任意の隣接する2頂点は、ちょうど λ 個の近傍を共有する。 * 任意の隣接しない2頂点は、ちょうど μ 個の近傍を共有する。 の2条件を満たすことを言う。このようなグラフは srg(v, k, λ, μ) と表されることがある。強正則グラフはによって1963年に導入された。 著者によっては、条件を自明に満たすグラフ、つまり、完全グラフおよび頂点数が同一の複数の完全グラフの非交和から成るグラフと、それらの補グラフ（同一個数の独立集合の集まりからできる完全）を強正則グラフに含めないこともある。 強正則グラフ srg(v, k, λ, μ) の補グラフはまた強正則グラフ、srg(v, v−k−1, v−2−2k+μ, v−2k+λ) になる。 強正則グラフは μ が0でないとき、直径2の（distance-regular graph）である。強正則グラフは λ が1であるとき、（locally linear graph）である。