強正則グラフ
強正則グラフの隣接行列はちょうど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]} である。
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ドルを提示した。