An efficient algorithm to recognize locally equivalent graphs (Q1181011): Difference between revisions

To locally complement a graph \(G\) at a vertex \(v\) is to replace the subgraph induced by \(G\) on \(\Gamma(v)\) by the complementary subgraph. Two graphs are locally equivalent if they can be transformed one into the other by a sequence of local complementations. A polynomial time algorithm is given to decide whether two graphs \(G\), \(G'\) are locally equivalent.