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_iq_j^{-1}\) and \(q_iq_k^{-1}\), where \(i, j, k \in V\) are distinct vertices, often force \(G\) and \(H\) to be isomorphic.