2
$\begingroup$

It is well-known that the Paley graph $P(q)$ is a strongly regular graph with parameters $(4t+1,2t,t-1,t)$. Suppose that $v$ is a vertex in the Paley graph $P(q)$. Suppoe that $C$ is the set of all neighbours of $v$ and $D$ be the complement of $C$. If one applies Godsil-Mckay switching, then under what conditions the new graph is non-isomorphic to the Paley graph $P(q)$?

$\endgroup$

1 Answer 1

3
$\begingroup$

If you apply what I call local switching to $C$, then the graph that results can be obtained by Seidel switching as follows. Let $Y$ be the Paley graph with an extra isolated vertex. Apply Seidel switching to set $C$, to get a new graph $Y'$. Then $Y'$ still has an isolated vertex, the remaining vertices induce a graph isomorphic to $P(q)$. (This is a property of the switching class of $P(q)\cup K_1$.)

The key here is that in $P(q)$, each vertex not in $C\cup\nu$ is joined to exactly half the vertices in $C$.

For the benefit of outsiders, if $C$ is subset of the vertices of a graph $X$ the Seidel switching on $C$ produces the graph $Y$ on the same vertex set, where if $x\in C$ and $y\notin C$ then $xy$ is an edge in $Y$ if and only if it is not an edge in $X$. If $X$ and $Y$ are regular with the same valency, they are cospectral.

For local switching choose $C$ so that the subgraph it induces is regular and each vertex not in $C$ is adjacent to all, none, or exactly half the vertices in $C$. Now for each vertex half-joined to $C$, delete those edges joining it to $C$ and the the complementary set. Again the new graph is cospectral to the original graph, and is often not isomorphic to it. (It's going to be really embarrassing if I made a mistake in this description.)

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .