Note on the reconstruction of infinite graphs with a fixed finite number of components

✍ Scribed by Thomas Andreae

• Publisher: John Wiley and Sons
• Year: 1982
• Tongue: English
• Weight: 169 KB
• Volume: 6
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190060109

✦ Synopsis

For every positive integer c , we construct a pair G, , H, of infinite, nonisomorphic graphs both having exactly c components such that G, and H, are hypomorphic, i.e., G, and H, have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G,, H , is an example for a pair of non-isomorphic, hypomorphic, connected graphs also having connected complements-a property not shared by any of the previously known counterexamples to the reconstruction conjecture for infinite graphs.

Two graphs G and H are called hypomorphic if there exists a bijection

The reconstruction conjecture asserts that G sx Hfor every pair of hypomorphic graphs G and H with more than two vertices. The conjecture is open for finite graphs and false for infinite graphs. Many counterexamples to the reconstruction conjecture for infinite graphs occur in [l], [3], [4], [ 5 ] , [7], and [8]; however, all these examples of nonisomorphic, hypomorphic graphs G and H share one common property: If G has exactly c components for a positive integer c, then the number of components of H i s different from c. Thus, in their survey article [2] Bondy and Hemminger posed a problem (Problem 16 in the list of unsolved problems in [2]) which can be reformulated as follows: Is it true that G H holds for every pair of hypomorphic, infinite graphs G and H with a fixed finite number c = c(G) = c(H) of components? Since hypomorphic graphs have hypomorphic complements one gets a quick negative answer for the case c = 1, a fact first mentioned in [6] by Nash-Williams: Let T be the regular tree of degree No; further, let us write mA for the disjoint union of m copies of A (where m is a cardinal and A is a