Strongly Regular Graph

Definition

A strongly regular graph (SRG) is a regular graph $G=(V,E)$ with $v$ vertices and degree $k$ such that for some given integers $\lambda ,\mu \ge 0$:

• every two adjacent vertices have $\lambda$ common neighbors, and
• every two non-adjacent vertices have $\mu$ common neighbors.

Such a strongly regular graph is denoted by $\mathrm{srg}(v,k,\lambda ,\mu )$.

Proposition

Let $G=\mathrm{srg}(\nu ,k,\lambda ,\mu )$. Then its complement graph is also a strongly regular graph

$$\mathrm{srg}(v,v-k-1,v-2-2k+\mu ,v-2k+\lambda ).$$

Proposition

The parameters $v,k,\lambda ,\mu$ obey the following relation

$$(v-k-1)\mu =k(k-\lambda -1).$$

\begin{proof} Fix a vertex $x$. Count pairs $(y,z)$ with $x\sim y\sim z\nsim x$.

• Count 1: $k$ choices for $y$, $k-\lambda -1$ choices for $z$;
• Count 2: $v-k-1$ choices for $z$, $\mu$ choices for $y$.

Now we finish the proof. \end{proof}

Proposition

The nontrivial eigenvalues are

$$r,s=\frac{(\lambda -\mu )\pm \sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}{2}.$$

Their multiplicities are

$$f=\frac{1}{2}\left((v-1)-\frac{2k+(v-1)(\lambda -\mu )}{\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}\right),$$

and

$$g=\frac{1}{2}\left((v-1)+\frac{2k+(v-1)(\lambda -\mu )}{\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}\right).$$

\begin{proof} Let $A$ be the adjacent matrix of $G$. Then $A^2=kI+\lambda A+\mu (J-I-A)$. Note that $\vec{j}=(1,\cdots ,1{)}^T$ is an eigenvector of $A$, then we take an orthogonal subspace $W$ of $⟨\vec{j}⟩$.

\begin{proof} Let $A$ be the adjacency matrix of $G$. Since $G$ is strongly regular with parameters $(v,k,\lambda ,\mu )$, we have

$$A^2=kI+\lambda A+\mu (J-I-A)=(k-\mu )I+(\lambda -\mu )A+\mu J.$$

Since $G$ is $k$-regular, $\vec{j}=(1,\dots ,1{)}^T$ is an eigenvector of $A$ with eigenvalue $k$. Now consider the subspace $W=⟨\vec{j}{⟩}^{\perp }$. For any $x\in W$, we have $Jx=0$. Also, since $A$ is symmetric and $A\vec{j}=k\vec{j}$, the subspace $W$ is $A$-invariant. Hence if $x\in W$ is an eigenvector of $A$ with eigenvalue $\theta$, then applying the identity above to $x$ gives

$$A^{2}x=(k-\mu )x+(\lambda -\mu )Ax+\mu Jx.$$

Since $Jx=0$ and $Ax=\theta x$, we get

$${\theta }^{2}x=(k-\mu )x+(\lambda -\mu )\theta x.$$

Thus

$${\theta }^2-(\lambda -\mu )\theta -(k-\mu )=0.$$

Therefore the two nontrivial eigenvalues are the two roots of this quadratic equation:

$$r,s=\frac{(\lambda -\mu )\pm \sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}{2}.$$

It remains to compute their multiplicities. Let $f$ and $g$ be the multiplicities of $r$ and $s$, respectively. Since $A$ has eigenvalue $k$ on $⟨\vec{j}⟩$ and eigenvalues $r,s$ on $W$, we have

$$1+f+g=v,k+fr+gs=0.$$

Therefore,

$$f=\frac{-k-(v-1)s}{r-s},g=\frac{k+(v-1)r}{r-s}.$$

Now the proof completes. \end{proof}