# Algorithm to recognize Strongly Regular Graph (SRG)

I am looking for an algorithm to determine whether a graph is Strongly Regular Graph (SRG) or not.

• There is no need for your first step, which also seems a bit too much to ask (how do you determine $\lambda,\mu$ from a single equation?). – Yuval Filmus Apr 28 '15 at 1:34
• What have you tried? Where did you get stuck? What research have you done? We expect you to do a significant amount of research before asking, and to show us in the question what you've tried and what research you've done. – D.W. Apr 30 '15 at 22:45

There is a trivial $O(kn^2)$ algorithm:

1. Choose a vertex $v$ and calculate its degree $k$. Then verify that all other vertices have degree $k$.

2. Choose some neighbor $w$ of $v$ and calculate the number of common neighbors $\lambda$. Then verify that all other pairs of adjacent vertices have $\lambda$ common neighbors.

3. Choose some non-neighbor $x$ of $v$ and calculate the number of common neigbors $\mu$. Then verify that all other pairs of non-adjacent vertices have $\mu$ common neighbors.

If you like linear algebra, you can also compute the square $A^2$ of the adjacency matrix $A$. Then check that:

1. All diagonal entries of $A^2$ are equal to some constant $k$.

2. All off-diagonal entries $A^2_{ij}$ such that $A_{ij} = 1$ are equal to some constant $\lambda. 3. All off-diagonal entries$A^2_{ij}$such that$A_{ij} = 0$are equal to some constant$\mu$. This algorithm takes time$O(n^\omega)\$.