Strongly regular graph

The Paley graph of order 13, a strongly regular graph with parameters srg(13,6,2,3).
Graph families defined by their automorphisms
distance-transitive distance-regular strongly regular
symmetric (arc-transitive) t-transitive, t ≥ 2 skew-symmetric
(if connected)
vertex- and edge-transitive
edge-transitive and regular edge-transitive
vertex-transitive regular (if bipartite)
biregular
Cayley graph zero-symmetric asymmetric

In graph theory, a strongly regular graph is defined as follows. Let G = (V, E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:

• Every two adjacent vertices have λ common neighbours.
• Every two non-adjacent vertices have μ common neighbours.

A graph of this kind is sometimes said to be an srg(v, k, λ, μ). Strongly regular graphs were introduced by Raj Chandra Bose in 1963.[1]

Some authors exclude graphs which satisfy the definition trivially, namely those graphs which are the disjoint union of one or more equal-sized complete graphs,[2][3] and their complements, the complete multipartite graphs with equal-sized independent sets.

The complement of an srg(v, k, λ, μ) is also strongly regular. It is an srg(v, v−k−1, v−2−2k+μ, v−2k+λ).

A strongly regular graph is a distance-regular graph with diameter 2 whenever μ is non-zero. It is a locally linear graph whenever λ is one.

Properties

Relationship between Parameters

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]

Eigenvalues

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]

Examples

A strongly regular graph is called primitive if both the graph and its complement are connected. All the above graphs are primitive, as otherwise μ=0 or λ=k.