Local equivalence and isomorphism relation I have a question regarding the relation between the local equivalence of two graphs and how isomorphic they are. For the isomorphism , two graphs are isomorphic if there is a permutation matrix that can transform the one adjacency matrix to the other.
$\begin{equation}
A_{1}=PA_{2}P^{T} \,\,\text{where P is the permutation matrix}
\end {equation}$
The local equivalence is more tricky to me. André Bouchet's paper "An efficient algorithm to recognize locally equivalent graphs" (Combinatorica, 11(4), pp. 315-329) is about an algorithm that determines if two graphs are local equivalent. I just wonder if there is any relation of graph isomorphism and local equivalence.
 A: There is no relationship.
When two graphs are isomorphic, this means that from a graph theorist's point of view, they are the same graph, with different vertex names. All purely graph-theoretic properties of a graph (properties that can be determined from how the vertices are connected, without referring to vertex names, diagrams, etc.) are going to be the same for two isomorphic graphs.
From this point of view, local equivalence is not a purely graph-theoretic property: it attaches meaning to the vertex set. Two graphs with different vertex sets can never be locally equivalent, no matter how similar they are - even if they are isomorphic.
Moreover, even if two graphs are isomorphic and have the same vertex set, it is possible that they are still not locally equivalent. An example is found in Bouchet's paper Recognizing locally equivalent graphs (Discrete Mathematics, 1993):

This example is due to Fon-Der-Flaass and is also a counterexample to a stronger conjecture about local equivalence that I won't mention here.
Also, two locally equivalent graphs will usually not be isomorphic; even basic properties like the number of edges may be different.

P.S. The definition of local equivalence is obscure, so for the benefit of future readers I include it here.
If $v$ is a vertex of $G$, the local complement of $G$ at $v$, denoted $G * v$, is the graph obtained by replacing the subgraph of $G$ induced by the neighborhood of $v$ by its complement. Two graphs $G, G'$ with the same vertex set are locally equivalent if we can obtain $G'$ from $G$ by a sequence of local complement operations.  Because $(G * v) * v = G$, we can undo any local complement we take by another local complement; this makes this relationship symmetric.
