Strongly regular graph

The four parameters in an srg(v, k, λ, μ) are not independent and must obey the following relation:

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

The above relation can be derived very easily through a counting argument as follows:

1. Imagine the vertices of the graph to lie in three levels. Pick any vertex as the root, in Level 0. Then its k neighbors lie in Level 1, and all other vertices lie in Level 2.
2. Vertices in Level 1 are directly connected to the root, hence they must have λ other neighbors in common with the root, and these common neighbors must also be in Level 1. Since each vertex has degree k, there are ${\displaystyle k-\lambda -1}$ edges remaining for each Level 1 node to connect to nodes in Level 2. Therefore, there are ${\displaystyle k\times (k-\lambda -1)}$ edges between Level 1 and Level 2.
3. Vertices in Level 2 are not directly connected to the root, hence they must have μ common neighbors with the root, and these common neighbors must all be in Level 1. There are ${\displaystyle (v-k-1)}$ vertices in Level 2, and each is connected to μ nodes in Level 1. Therefore the number of edges between Level 1 and Level 2 is ${\displaystyle (v-k-1)\times \mu }$.
4. Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.

Let I denote the identity matrix and let J denote the matrix of ones, both matrices of order v. The adjacency matrix A of a strongly regular graph satisfies two equations. First:

${\displaystyle AJ=JA=kJ,}$

which is a trivial restatement of the regularity requirement. This shows that k is an eigenvalue of the adjacency matrix with the all-ones eigenvector. Second is a quadratic equation,

${\displaystyle {A}^{2}=k{I}+\lambda {A}+\mu ({J-I-A})}$

which expresses strong regularity. The ij-th element of the left hand side gives the number of two-step paths from i to j. The first term of the RHS gives the number of self-paths from i to i, namely k edges out and back in. The second term gives the number of two-step paths when i and j are directly connected. The third term gives the corresponding value when i and j are not connected. Since the three cases are mutually exclusive and collectively exhaustive, the simple additive equality follows.

Conversely, a graph whose adjacency matrix satisfies both of the above conditions and which is not a complete or null graph is a strongly regular graph.[4]

The adjacency matrix of the graph has exactly three eigenvalues:

• k, whose multiplicity is 1 (as seen above)
• ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}$ whose multiplicity is ${\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$
• ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}$ whose multiplicity is ${\displaystyle {\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$

As the multiplicities must be integers, their expressions provide further constraints on the values of v, k, μ, and λ, related to the so-called Krein conditions.

Strongly regular graphs for which ${\displaystyle 2k+(v-1)(\lambda -\mu )=0}$ are called conference graphs because of their connection with symmetric conference matrices. Their parameters reduce to

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

Strongly regular graphs for which ${\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}$ have integer eigenvalues with unequal multiplicities.

Conversely, a connected regular graph with only three eigenvalues is strongly regular.[5]

The strongly regular graphs with λ = 0 are triangle free. Apart from the complete graphs on less than 3 vertices and all complete bipartite graphs the seven listed above (pentagon, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22, and Higman-Sims) are the only known ones. Strongly regular graphs with λ = 0 and μ = 1 are Moore graphs with girth 5. Again the three graphs given above (pentagon, Petersen, and Hoffman-Singleton), with parameters (5, 2, 0, 1), (10, 3, 0, 1) and (50, 7, 0, 1), are the only known ones. The only other possible set of parameters yielding a Moore graph is (3250, 57, 0, 1); it is unknown if such a graph exists, and if so, whether or not it is unique.[8]

More generally, every strongly regular graph with ${\displaystyle \mu =1}$ is a geodetic graph, a graph in which every two vertices have a unique unweighted shortest path.[9] The only known strongly regular graphs with ${\displaystyle \mu =1}$ are the Moore graphs. It is not possible for such a graph to have ${\displaystyle \lambda =1}$, but other combinations of parameters such as (400, 21, 2, 1) have not yet been ruled out. Despite ongoing research on the properties that a strongly regular graph with ${\displaystyle \mu =1}$ would have,[10][11] it is not known whether any more exist or even whether their number is finite.[9]