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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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