The Reconstruction Conjecture for finite simple graphs and associated directed graphs

Abstract

In this paper, we study the Reconstruction Conjecture for finite simple graphs. Let $\Gamma$ and ${\Gamma }^{\prime }$ be finite simple graphs with at least three vertices such that there exists a bijective map $f:V(\Gamma )\to V({\Gamma }^{\prime })$ and for any $v\in V(\Gamma )$, there exists an isomorphism ${\varphi }_v:\Gamma -v\to {\Gamma }^{\prime }-f(v)$. Then we define the associated directed graph $\tilde{\Gamma }=\tilde{\Gamma }(\Gamma ,{\Gamma }^{\prime },f,\{{\varphi }_v{\}}_{v\in V(\Gamma )})$ with two kinds of arrows from the graphs $\Gamma$ and ${\Gamma }^{\prime }$, the bijective map $f$ and the isomorphisms $\{{\varphi }_v{\}}_{v\in V(\Gamma )}$. By investigating the associated directed graph $\tilde{\Gamma }$, we study when are the two graphs $\Gamma$ and ${\Gamma }^{\prime }$ isomorphic.

26 pages, 16 figures