✦ LIBER ✦

On the reconstruction of rayless infinite forests

✍ Scribed by Thomas Andreae; Rüdiger Schmidt

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 869 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080309

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph G is called strongly p‐reconstructible if it is (up to isomorphism) uniquely determined by the collection of its pairwise nonisomorphic subgraphs G – v where v is a pendent vertex of G. Using previous results of the second author concerning the structure of infinite rayless graphs it is shown that every rayless forest with an infinite edge‐set is strongly p‐reconstructible. This result is applied to the classical reconstruction problem to find that every infinite rayless forest G with a finite number of components is reconstructible; i.e., G is (up to isomorphism) uniquely determined by its collection of vertex‐deleted subgraphs. Furthermore, an example is given which shows that nonreconstructible rayless forests with a countable number of components exist.

📜 SIMILAR VOLUMES

Note on the reconstruction of infinite g

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

✍ Thomas Andreae 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 1 views

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

Reconstructing the degree sequence and t

Reconstructing the degree sequence and the number of components of an infinite graph

✍ Thomas Andreae 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 812 KB

We prove that the degree sequence of an infinite graph is reconstructibjle from its family of vertex-deleted subgraphs. Furthermore, as another result concerning the reconstruction of infinite graphs, we prove that the number c(G) of components of an infinite graph G is re~ons~uct~b~e if there is at

On the girth of infinite graphs

✍ Norbert Seifter 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 599 KB

Let X be an infinite k-valent graph with polynomial growth of degree d, i.e. there is an integer d and a constant c such that fx(n) 3, d> 1, 123, there exist k-valent connected graphs with polynomial growth of degree d and girth greater than 1. This means that in general the girth of graphs with pol

On the reconstruction of linear codes

✍ Philip Maynard; Johannes Siemons 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 2 views

For a linear code over GF (q) we consider two kinds of ''subcodes'' called residuals and punctures. When does the collection of residuals or punctures determine the isomorphism class of the code? We call such a code residually or puncture reconstructible. We investigate these notions of reconstructi

Reconstructing the number of copies of a

Reconstructing the number of copies of a valency-labeled finite graph in an infinite graph

✍ A. J. H. King; C. St. J. A. Nash-Williams 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 489 KB 👁 1 views

## Abstract Suppose that __G, H__ are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that __G__ ‐ ξ ≅ H ‐ Ψ(ξ) for every ξ ∼ __V__(G). Let __J__ be a finite graph and /(π) be a cardinal number for each π ≅ __V__(J). Suppose also that either /(π) is infinite for every π ≅ __V__(J) or _

On the notion of infinite Hamiltonian gr

On the notion of infinite Hamiltonian graph

✍ R. Halin 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract Based on the terms “end” and “cofinal spanning subtree” a general notion of Hamiltonicity of infinite graphs is developed. It is shown that the cube of every connected locally finite graph is Hamiltonian in this generalized sense.