Bowler, Nathan; Erde, Joshua; Heinig, Peter; Lehner, Florian; Pitz, Max Non-reconstructible locally finite graphs. (English) Zbl 1397.05116 J. Comb. Theory, Ser. B 133, 122-152 (2018). Summary: Two graphs \(G\) and \(H\) are hypomorphic if there exists a bijection \(\varphi : 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\).C. S. J. A. Nash-Williams [Discrete Math. 92, No. 1–3, 227–249 (1991; Zbl 0746.05046)] proved that all locally finite connected graphs with a finite number \(\geqslant 2\) of ends are reconstructible, and asked whether locally finite connected graphs with one end or countably many ends are also reconstructible.In this paper we construct non-reconstructible connected 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. Cited in 2 Documents MSC: 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) Keywords:reconstruction conjecture; reconstruction of locally finite graphs; extension of partial isomorphisms; promise structure Citations:Zbl 0746.05046 PDFBibTeX XMLCite \textit{N. Bowler} et al., J. Comb. Theory, Ser. B 133, 122--152 (2018; Zbl 1397.05116) Full Text: DOI arXiv References: [1] Andreae, T., On the reconstruction of locally finite trees, J. Graph Theory, 5, 2, 123-135, (1981) · Zbl 0426.05038 [2] Bondy, J. A.; Hemminger, R., Reconstructing infinite graphs, Pacific J. Math., 52, 2, 331-340, (1974) · Zbl 0295.05125 [3] Bondy, J. A.; Hemminger, R. L., Graph reconstruction - a survey, J. Graph Theory, 1, 3, 227-268, (1977) · Zbl 0375.05040 [4] Bowler, N.; Erde, J.; Heinig, P.; Lehner, F.; Pitz, M., A counterexample to the reconstruction conjecture for locally finite trees, Bull. Lond. Math. Soc., 49, 4, 630-648, (2018) · Zbl 1370.05153 [5] Diestel, R., Graph theory, (2010), Springer · Zbl 1204.05001 [6] Diestel, R., Locally finite graphs with ends: a topological approach, I. basic theory, Discrete Math., 311, 15, 1423-1447, (2011) · Zbl 1223.05198 [7] Harary, F.; Schwenk, A. J.; Scott, R. L., On the reconstruction of countable forests, Publ. Inst. Math., 13, 27, 39-42, (1972) · Zbl 0242.05101 [8] Nash-Williams, C. St. J.A., Reconstruction of locally finite connected graphs with at least three infinite wings, J. Graph Theory, 11, 4, 497-505, (1987) · Zbl 0652.05039 [9] Nash-Williams, C. St. J.A., Reconstruction of infinite graphs, Discrete Math., 95, 1, 221-229, (1991) · Zbl 0759.05066 [10] Nash-Williams, C. St. J.A., Reconstruction of locally finite connected graphs with two infinite wings, Discrete Math., 92, 1, 227-249, (1991) · Zbl 0746.05046 [11] Thomassen, C., Reconstructing 1-coherent locally finite trees, Comment. Math. Helv., 53, 1, 608-612, (1978) · Zbl 0391.05040 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.