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}(\nu ,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).$$