2
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Are you also assuming that the graphs are regular? (This is usually assumed for strongly regular graphs, excluding examples such as $K_{1,s}$.) $\endgroup$ – Misha Lavrov Oct 18 '17 at 16:04
  • $\begingroup$ Yes. Graphs are assumed to be regular. $\endgroup$ – John Smith Oct 19 '17 at 0:41
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.