Premium
Note on the reconstruction of infinite graphs with a fixed finite number of components
Author(s) -
Andreae Thomas
Publication year - 1982
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190060109
Subject(s) - combinatorics , mathematics , counterexample , conjecture , vertex (graph theory) , integer (computer science) , discrete mathematics , graph , computer science , programming language
For every positive integer c , we construct a pair G c , H c of infinite, nonisomorphic graphs both having exactly c components such that G c and H c are hypomorphic, i.e., G c and H c have the same families of vertex‐deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G 1 , H 1 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.