%-----------------------------------------------------------------------
% Beginning of chap5.tex
%-----------------------------------------------------------------------
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{STRONGLY REGULAR CAYLEY GRAPHS}
\label{cha:graphs}

\vspace{-12pt}
\section{Assuptions}\label{sec:assump}

We assume throughout this section that $G$ is a finite group and $S$ is subset of $G$. The \textbf{Cayley graph} with respect to G is the graph $\Gamma = \Gamma (G,S)$ such that the vertex set $V$ is exactly the members of $G$ and, for all vertices $x,y\in V$,  $x$ is adjacent to $y$ if and only if $y = sx$ for some $s\in S$.

For this paper, we consider only \textbf{simple} Cayley graphs. To achieve this, we choose our set $S$ so that the identity element of $G$ is not in $S$ and if $s\in S$ then $s^{-1}\in S$. In addition to being simple, based on the group structure built into a Cayley graph, we note that our graphs are all regular.

A special type of regular graph, called strongly regular, was first introduced by  R.C. Bose in 1963 \cite{BCN}. Given a regular graph with $v$ vertices of degree $k$, we can define a \textbf{strongly regular graph}, denoted $SRG(v,k,\lambda, \mu)$, to be such that there exist integers $\lambda$ and $\mu$ satisfying that every pair of adjacent vertices have $\lambda$ common neighbors and every pair of non-adjacent vertices have $\mu$ common neighbors. Probably the most famous example of a strongly regular graph is the Petersen graph, which is a $SRG(10,3,0,1)$:

\begin{figure}[htb]
\begin{center}
\includegraphics[scale=0.1]{PetersenGraph.pdf}\label{Fig:1}
\caption{Petersen Graph}
\end{center}
\end{figure}

We can see here that the Petersen graph is a connected graph which satisfies the definition of a strongly regular graph, where adjacent vertices do not have common neighbors and non-adjacent vertices have one common neighbor. Let's recall that the Petersen graph is the complement of the line graph of the complete graph on five vertices, which is connected.  For connected strongly regular graphs whose complements are also connected, we have the following bounds on their parameters: $$0<\mu<k<v-1$$
Considering further the complement of a strongly regular graph, if we have a graph $\mathcal{G} = SRG(v,k,\lambda,\mu)$, then its complement is $\overline{\mathcal{G}} = SRG(v, v-k-1, v-2k+\mu-2,v-2k+\lambda)$. Because our parameters are non-negative, this tells us that $$v-2k+\mu-2 \geq 0$$

\section{Lemma}\label{sec:lemma}
We can more carefully consider the structure of strongly regular graphs to develop the next lemma which specifies under what parameters we may construct a strongly regular graph.

\begin{lemma}\label{lem:1}
For a strongly regular graph $\mathcal{G} = SRG(v,k,\lambda,\mu)$, $$k(k-\lambda - 1) = \mu (v-k-1)$$
\end{lemma}
\begin{proof}
Fix a vertex $x$ in $\mathcal{G}$, and consider the set $E := \{(y,z): y~z,\; x~y \; x\nsim z\}$. We can computer the order of $E$ in two different ways.

First, by counting the number of vertices of $\mathcal{G}$ which are distance 2 from $x$. Because the degree of $x$ is $k$ and the diameter of $\mathcal{G}$ is 2, there are $v-k-1$ vertices distance 2 from $x$.  Note that $\mu$ counts the number of common neighbors of non-adjacent vertices. Thus, $$|E| = \mu (v-k-1)$$ Now, let's determine the order of $E$ by first counting the number of vertices of $\mathcal{G}$ which are adjacent to $x$ not having a common neighbor with $x$. Recall that $\lambda$ counts the number of common neighbors of adjacent vertices. Thus, there are $k-\lambda -1$ vertices of $\mathcal{G}$ adjacent to $x$ and not adjacent to a neighbor of $x$. Because the degree of $\mathcal{G}$ is $k$, $$|E| = k(k - \lambda - 1).$$
\end{proof}

\endinput

%-----------------------------------------------------------------------
% End of chap5.tex
%-----------------------------------------------------------------------
