距离无爪图的Hamilton性  

The hamiltonian of distance claw-free graphs

作　　者：王兵[1] 

机构地区：[1]枣庄师范专科学校数学系 山东枣庄　277160

出　　处：《安徽大学学报（自然科学版）》2004年第1期20-23,29,共5页Journal of Anhui University(Natural Science Edition)

摘　　要：距离无爪图类属于无爪图类。所谓距离无爪图是对图中的每一个顶点,其距离为的邻域的独立数均不超过3的图.F.BruceShephed已证明:若G是距离无爪图且G是2─连通的,则G有Hamilton路;若G是距离无爪图且G是3─连通的,则G有Hamilton圈.本文在此基础上,定义了一种新的禁用子图──网全爪,首先证明了2-连通的、无网的距离无爪图有Hamilton圈.又证明了2-连通的有网、无网全爪的距离无爪图有Hamilton圈.Distance claw-free consists of those claw-free graphs such that for each vertex v, the set of vertices at distance i from v does not contain an independent subset of size three.F.Bruce shepherd has proved that: if G∈DC and G is 2-connected, then G has a Hamilton path,furthermore,if G∈DC and G is 3-connected then G has a Hamilton path.Basing on these results, the paper defines a new forbidden subgraph,which is net completed-claw. The paper proves the 2-connected、distance claw-free graph has hamilton cycle on the conditions of net-free or net complete claw -free.

关 键 词：距离无爪图 网全爪 HAMILTON圈 无向简单图 

分 类 号：O157.5[理学—数学]