Non-reconstructible locally finite graphs

Abstract

Two graphs $G$ and $H$ are \emph{hypomorphic} if there exists a bijection $\phi :V(G)\to V(H)$ such that $G-v\cong H-\phi (v)$ for each $v\in V(G)$. A graph $G$ is \emph{reconstructible} if $H\cong G$ for all $H$ hypomorphic to $G$. Nash-Williams proved that all locally finite graphs with a finite number $\ge 2$ of ends are reconstructible, and asked whether locally finite graphs with one end or countably many ends are also reconstructible. In this paper we construct non-reconstructible graphs of bounded maximum degree with one and countably many ends respectively, answering the two questions of Nash-Williams about the reconstruction of locally finite graphs in the negative.

Figure 1 updated and minor typographical errors corrected