×

Non-reconstructible locally finite graphs. (English) Zbl 1397.05116

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.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Citations:

Zbl 0746.05046
PDFBibTeX XMLCite
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.