K_(1,4)-受限图的最长路  

Longest Paths in K_(1,4)-restricted Graphs

作　　者：尤海燕[1] 赵强[2] 

机构地区：[1]山东建筑大学理学院,济南山东250101 [2]山东师范大学数学科学学院,济南山东250014

出　　处：《数学进展》2011年第3期270-274,共5页Advances in Mathematics（China）

基　　金：国家自然科学基金项目(No.11001155);山东省自然科学基金项目(No.Q2008A04);山东省博士基金(No.BS2010SW030).

摘　　要：图G中同构于K_(1,p)的子图叫G的p-爪(p≥3).如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥p-2,则称G为K(1,p-)-受限图,它是无爪图(p=3)时的推广.本文证明了:连通的K_(1,4-)受限图G,若|G|≥7,则G有Hamilton路或有长至少为2δ+2的路.A subgraph isomorphic to Kl,p in graph G is called a p-claw of G（p≥3）. A graph G is said to be K1,p-restricted if for any p-claw H in G, the number of edges（in G） among vertices with degree 1 in H is at least p - 2. Clearly, every claw-free graph is K1,p-restricted （p = 3）. In this paper, we prove that connected Kl,n-restricted graph G with ｜G｜ 〉 7 has a Hamilton path or a path of length at least 2δ ＋ 2.

关 键 词：K1 p-受限图 连通图 路 

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