A Note on Graph Reconstruction

Abstract

Suppose $G$ and $G^{\prime }$ 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^{\prime }-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^{\prime }$. 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\}\ne \{x,y\}$ and $G-\{x,y\}$ is isomorphic to $G-\{u,v\}$.