首页 | 本学科首页   官方微博 | 高级检索  
     


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:
  1. 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.
  2. 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号