Strongly Regular Graphs
A graph \(G\) is called strongly regular with parameters \((n, k, s, t)\) if \(G\) is a \(n\)-vertex, \(k\)-regular graph such that any two adjacent vertices have \(s\) common neighbors and any two non-adjacent vertices have \(t\) common neighbors.
If \(G\) is strongly regular with parameters \((n,k,s,t)\) then \(\overline{G}\) is strongly regular with parameters \((n,\overline{k}, \overline{s}, \overline{t})\) where
\begin{align*}
\overline{k} &= n-k-1\\
\overline{s} &= n-2-2k+t\\
\overline{t} &= n-2k+s
\end{align*}
It is clear that \(\overline{k} = n-k-1\). Let \(v_i\) and \(v_j\) be two adjacent vertices in \(G\), and thus \(v_j\) and \(v_j\) are non-adjacent in \(\overline{G}\). In \(G\), let \(\Omega_i\) be the vertices adjacent to \(v_i\) that are not adjacent to \(v_j\) and let \(\Omega_j\) be the vertices adjacent to \(v_j\) that are not adjacent to \(v_i\), and let \(\Gamma_{i,j}\) be the set of vertices not adjacent to neither \(v_i\) nor \(v_j\). Therefore, in \(\overline{G}\) the non-adjacent vertices \(v_i\) and \(v_j\) have \(|\Gamma_{i,j}|\) common neighbors. Since \(|\Omega_i| = |\Omega_j| = k-s-1\) and \(\Omega_i\cap \Omega_j = \emptyset\) we have
\[
n = |\Gamma_{i,j}| + |\Omega_i| + |\Omega_j| + s + 2
\]
from which it follows that \(|\Gamma_{i,j}| = n-2k+s\). Hence, in \(\overline{G}\), any non-adjacent vertices have \(\overline{t} = n-2k+s\) common neighbors. The formula for \(\overline{s}\) is left as an exercise (Exercise 5.1).
Let \(G\) be a strongly regular graph with parameters \((n,k,s,t)\) and suppose that \(G\) is not the complete graph. Prove that \(G\) is connected if and only if \(t \gt 0\). In this case, deduce that \(\diam(G)=2\).
Let \(G\) be a strongly regular graph with parameters \((n,k,s,t)\). Then
\begin{equation}
\bs{A}^2 = k\bs{I} + s\bs{A} + t(\bs{J}-\bs{I}-\bs{A})
\end{equation}
The \((i,j)\) entry of \(\bs{A}^2\) is the number of walks of length 2 from \(v_i\) to \(v_j\). If \(v_i\) and \(v_j\) are adjacent then they have \(s\) common neighbors and each such neighbor determines a walk from \(v_i\) to \(v_j\) of length 2. On the other hand, if \(v_i\) and \(v_j\) are non-adjacent then they have \(t\) common neighbors and each such neighbor determines a walk from \(v_i\) to \(v_j\) of length 2. If \(v_i=v_j\) then the number of walks from \(v_i\) to \(v_j\) is \(k\). Hence,
\[
(\bs{A}^2)_{i,j} = \begin{cases}
s, & v_iv_j \in E(G)\\
t, & v_iv_j \notin E(G)\\
k, & i=j
\end{cases}
\]
This yields the desired formula for \(\bs{A}^2\).
The adjacency matrix of a strongly regular graph has only three eigenvalues. If \(G\) is a strongly regular graph with parameters \((n,k,s,t)\) then the eigenvalues of \(\bs{A}\) besides \(k\) are
\begin{align*}
\alpha &= \frac{(s-t) + \sqrt{\Delta}}{2}\\
\beta &= \frac{(s-t) - \sqrt{\Delta}}{2}
\end{align*}
where \(\Delta=(s-t)^2 + 4(k-t)\), with algebraic multiplicities
\begin{align*}
m_{\alpha} = \frac{1}{2}\left((n-1) - \frac{2k+(n-1)(s-t)}{\sqrt{\Delta}}\right)\\[2ex]
m_{\beta} = \frac{1}{2}\left((n-1) + \frac{2k+(n-1)(s-t)}{\sqrt{\Delta}}\right)
\end{align*}
Let \(\bs{z}\) be an eigenvector of \(\bs{A}\) corresponding to an eigenvalue \(\lambda\) not equal to \(k\). Then \(\bs{z}\) is orthogonal to the all ones vector and thus \(\bs{J}\bs{z}=\bs{0}\). Then from \eqref{eqn:A2-str} we have \(\bs{A}^2 - (s-t)\bs{A} - (k-t)\bs{I} = t\bs{J}\) and therefore
\[
(\lambda^2 - (s-t)\lambda - (k-t))\bs{z} = 0
\]
and therefore \(\lambda^2 - (s-t)\lambda - (k-t) = 0\). The roots of the polynomial \(x^2 - (s-t)x - (k-t)=0\) are precisely \(\alpha\) and \(\beta\). Since \(\tr(\bs{A})\) is the sum of the eigenvalues of \(\bs{A}\), \(\tr(\bs{A})=0\), and \(k\) has multiplicity one, we have \(m_{\alpha} + m_{\beta} = n-1\) and \(\alpha m_\alpha + \beta m_\beta + k = 0\). Solving these equations for \(m_\alpha\) and \(m_\beta\) yield \(m_\alpha = - \frac{(n-1)\beta + k}{\alpha-\beta}\) and \(m_{\beta} = \frac{(n-1)\alpha+k}{\alpha-\beta}\), and substituting the expression for \(\alpha\) and \(\beta\) yield stated expressions.
Exercises
Finish the proof of Lemma 5.1.1.