The reconstruction problem for certain infinite graphs |
| |
Authors: | Michael v. Rimscha |
| |
Affiliation: | 1. Institut für Informatik, Universit?t Stuttgart, Azenbergstrasse 12, 7000, Stuttgart, BRD
|
| |
Abstract: | We are concerned with the notion of the degree-type (D G i )i∈ω of a graphG, whereD G i is defined to be the number of vertices inG with degreei. In the first section the following results are proven: - IfG is a connected, locally finite, countably infinite graph such that there exists ani so thatD G i andD G i+1 are both finite and different from 0, thenG is reconstructible.
- Locally finite, countably infinite graphsG, for which infinitely manyD G i are different from 0 but only finitely manyD G i are infinite, are reconstructible.
In the second section we give some results about the reconstructibility of certain locally finite countably infinite interval graphs and show that a reconstruction of a planar, infinite graph has to be planar too. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|