图的最小度与路可扩性.pdfVIP

10 11 2010 4 科 学 技 术 与 工 程 Vol. 10 No. 11 Apr. 2010 第 卷 第 期 年 月 167 1-1815 (2010)11-2690-04 Science Technology and Engineering  2010 Sci. Tech. Engng. 图的最小度与路可扩性 滕 岩 王江鲁 ( ， 2500 14 ) 山东师范大学数学科学学院 济南 G ， (G) + 1， G 。 (G) 摘 要 讨论了图的最小度与路可扩之间的关系 得到当δ ≥ 则图 是路可扩的 这里δ 的下界是最好可 2 能的。 关键词 顶点的度 路可扩 最小度 中图法分类号 O157 . 5 ; 文献标志码 A 、 、 ， G Hamilton 。 仅讨论有限 无向 简单图 所使用的记号和术 则 有 圈 ， ［1］。 2 ［3 ］ G n 3 ， G 语约定如下 其中未加说明的部分请参照文献 定理 设图 的阶 ≥ 如果 中任意一 G ，V (G)、E (G) G u ，v d (u)+ d (v ) n ， G 设 是一个图 分别表示 的顶点 对不相邻的顶点 满足 ≥ 则 有 。 S ，T V (G)，a V (G) G Hamilton 圈。 集和边集 对  ∈ 及 的子图 H ， 1990 年，Hendry 发现已有的一些保证Hamilton 令 ， ， N (a)= {v S :va E (G)}，N (a)= N (a)， 圈存在的度型充分条件 实际上隐含着圈可扩性 S ∈ ∈ H V (H) d (a)= |N (a)| ，E (S ，T)= {xy E (G):x 并得到了如下结果。 H H ∈ ∈ 3 ［4 ］ G n 3 ， (G) S ，y T}。 定理 设图 的阶 ≥ 如果δ ≥ ∈ |H | = | V (H )| H 。d (a) n + 1 称为 的阶 G 也简记为 ， G 。 则 是完全圈可扩的