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


An edge-deletion problem for locally finite graphs
Authors:Thomas Andreae
Affiliation:Freie Universität Berlin, 2. Mathematisches Institut, 1000 Berlin 33, West Germany
Abstract:For each positive integer n, let Tn be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs Tn is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T2, the oneway infinite path T1 is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T1 is also the only stable graph.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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