VERTEX-SWITCHING, ISOMORPHISM, AND PSEUDOSIMILARITY

A vertex-switching G(s) of a graph G is obtained by deleting from G all edges of G with exactly one end in the set of vertices S, and then adding to G all edges of the complement of G with exactly one end in S. We characterize the situations in which G(s) is isomorphic to G, a result with application to the vertex-switching reconstruction problem. We use these results to construct pairs of vertex-switching pseudosimilar vertices, nonsimilar vertices u and upsilon in a graph G with G({u}) isomorphic to G({upsilon}). We show that every such pair can be constructed by our methods.