Definition Of Strongly Regular Graphs

Question

A graph $G$ is strongly regular if any pair of adjacent vertices have precisely $p$ common neighbours and any pair of nonadjacent vertices have precisely $q$ common neighbours.

Let us say a graph has property $X$ if any pair of adjacent vertices have precisely $p$ common neighbours and any pair of nonadjacent vertices have precisely $q$ common non-neighbours.

What graphs have property $X$?

Let us say a graph has property $Y$ if any pair of adjacent vertices have precisely $p$ common non-neighbours and any pair of nonadjacent vertices have precisely $q$ common neighbours.

What graphs have property $Y$?

For example, $C_4$, $C_5$, complete bipartite $K_{n,n}$ have all three properties ($X$, $Y$, strongly regular).

$C_6$ isn't strongly regular, and it doesn't possess property $X$ or property $Y$ either.

What would be a graph having the strongly regular property but not property $X$? Or property $Y$?

Answer 1

Under the usual additional hypothesis — that a strongly regular graph is also regular — your four properties are all equivalent.

Suppose that all vertices in $G$ have degree $k$. If $v$ and $w$ are adjacent, then we can partition the remaining vertices of the graph into the four parts $$N_{vw}, \quad N_v, \quad N_w, \quad N_{\varnothing}$$ according to whether they are adjacent to both $v$ and $w$, just $v$, just $w$, and neither.

Regularity tells us that $|N_{vw}| + |N_v| = |N_{vw}| + |N_w| = k-1$; equivalently, $|N_v| + |N_\varnothing| = |N_w| + |N_\varnothing| = n-k-1$. Together with this, either of the two possible conditions you could impose on pairs of adjacent vertices would be enough to tell us the sizes of all four parts:

• If we know that any two adjacent vertices have $p$ common neighbors, then $|N_{vw}| = p$, so $|N_v| = |N_w| = k-p-1$, and therefore $|N_\varnothing| = n-2k+p$.
• If we know that any two adjacent vertices have $p$ common non-neighbors, then $|N_\varnothing| = p$, so $|N_v| = |N_w| = n-k-p-1$, and therefore $|N_{vw}| = 2k+p-n$.

So the two conditions are equivalent (but with different values of $p$). Almost exactly the same thing happens with the two conditions on pairs of non-adjacent vertices.

As a result, all four possible combinations of a condition on neighbors and a condition on anti-neighbors, which superficially produce "strongly regular", "property $X$", "property $Y$", "strongly regular complement", actually produce the same class of graphs.