A Note on Graph Reconstruction

Xuding Zhu1
1Department of Mathematics and Statistics Simon Fraser University Burnaby, BC V5A 186

Abstract

Suppose \(G\) and \(G’\) are graphs on the same vertex set \(V\) such that for each \(v \in V\) there is an isomorphism \(\theta_x\) of \(G-v\) to \(G’-v\). We prove in this paper that if there is a vertex \(x \in V\) and an automorphism \(\alpha\) of \(G-x\) such that \(\theta_x\) agrees with \(\alpha\) on all except for at most three vertices of \(V-x\), then \(G\) is isomorphic to \(G’\). As a corollary we prove that if a graph \(G\) has a vertex which is contained in at most three bad pairs, then \(G\) is reconstructible. Here a pair of vertices \(x,y\) of a graph \(G\) is called a bad pair if there exist \(u,v \in V(G)\) such that \(\{u,v\} \neq \{x,y\}\) and \(G-\{x,y\}\) is isomorphic to \(G-\{u,v\}\).