Graph Reconstruction by Permutations

Abstract

Let $G$ and $H$ be graphs with a common vertex set $V$, such that $G–i\cong H–i$for all $i\in V$. Let $p_i$ be the permutation of $V–i$ that maps $G–i$ to $H–i$, and let $q_i$ denote the permutation obtained from $p_i$ by mapping $i$ to $i$. It is shown that certain algebraic relations involving the edges of $G$ and the permutations $q_i{q}_j^{-1}$ and $q_i{q}_k^{-1}$, where $i,j,k\in V$ are distinct vertices, often force $G$ and $H$ to be isomorphic.