pith. sign in

arxiv: 1606.02926 · v2 · pith:2VJPD2U2new · submitted 2016-06-09 · 🧮 math.CO

A counterexample to the reconstruction conjecture for locally finite trees

classification 🧮 math.CO
keywords conjecturegraphsreconstructiblecongcounterexamplefiniteharary-schwenk-scotthypomorphic
0
0 comments X
read the original abstract

Two graphs $G$ and $H$ are hypomorphic if there exists a bijection $\varphi \colon V(G) \rightarrow V(H)$ such that $G - v \cong H - \varphi(v)$ for each $v \in V(G)$. A graph $G$ is reconstructible if $H \cong G$ for all $H$ hypomorphic to $G$. It is well known that not all infinite graphs are reconstructible. However, the Harary-Schwenk-Scott Conjecture from 1972 suggests that all locally finite trees are reconstructible. In this paper, we construct a counterexample to the Harary-Schwenk-Scott Conjecture. Our example also answers four other questions of Nash-Williams, Halin and Andreae on the reconstruction of infinite graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.