Non-reconstructible locally finite graphs

被引：2

作者：

Bowler, Nathan ^{[1
]}

Erde, Joshua ^{[1
]}

Heinig, Peter ^{[1
]}

Lehner, Florian ^{[1
]}

Pitz, Max ^{[1
]}

机构：

[1] Dept Math, Bundesstr 55, D-20146 Hamburg, Germany

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2018年 / 133卷

关键词：

Reconstruction conjecture; Reconstruction of locally finite graphs; Extension of partial isomorphisms; Promise structure; CONNECTED GRAPHS; INFINITE-GRAPHS; WINGS; TREES;

D O I：

10.1016/j.jctb.2018.04.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Two graphs G and H are hypomorphic if there exists a bijection phi: V (G) -> V (H) such that G - v congruent to H - phi(v) for each v is an element of V (G). A graph G is reconstructible if H congruent to G for all H hypomorphic to G. Nash-Williams proved that all locally finite connected graphs with a finite number >= 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. (C) 2018 Elsevier Inc. All rights reserved.

引用

页码：122 / 152

页数：31

共 11 条

[1] ON THE RECONSTRUCTION OF LOCALLY FINITE TREES [J].