图的度和与扩路  

Extending Paths and Degree Sums in Graphs

作　　者：刘春房[1,2] 王江鲁[2] 

机构地区：[1]滨州学院数学与信息科学系,滨州山东256603 [2]山东师范大学数学科学学院,济南山东250014

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

基　　金：山东省高等学校科技计划项目(No.J101.A11.);山东科技大学"春蕾计划"项目(No.2010Azz053)

摘　　要：本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|<n的路P是可扩的.并且|P|的下界是最优的.In this paper, we study the relations between degree sums and extending paths in graphs. The following result is proved. Let G be a graph of order n. If d（u）＋d（v）≥n＋n/k（2≤k≤n-2）for each pair of nonadjacent vertices u,v in V（G）, then every path P of G with k＋1≤｜P｜〈n is extendable. The lower bound of ｜P｜ is sharp.

关 键 词：顶点的度 路可扩 HAMILTON路 

分 类 号：O211.1[理学—概率论与数理统计]