Pure Mathematics 理论数学, 2011, 1, 64-67 http://dx.doi.org/10.12677/pm.2011.12014 Published Online July 2011 (http://www.hanspub.org/journal/pm/) Copyright © 2011 Hanspub PM Extending Cycles and Degree Sums in Graphs Jianglu Wang, Jianmin Cheng School of Mathematical Sciences, Shandong Normal University, Jinan Email: yzhfzh@sina.com Received: Mar. 24th, 2011; revised: May 25th, 2011; accepted: Jun. 1st, 2011. Abstract: In this paper, we study the relations between degree sums and extending cycles in graphs. The fol- lowing result is proved. Let G be a graph of order . If 3n dudvn k for each pair of nonadjacent vertices u,v in , then every cycle C of G with VG 2 n kCn is extendable. By the result, we have that if 32 2 du dvn for each pair of nonadjacent vertices u, v in VG, then G is fully cycle extend- able. Keywords: Degree of Vertex; Extending Cycle 图的度和与扩圈 王江鲁,程建民 山东师范大学数学科学学院,济南 Email: yzhfzh@sina.com 收稿日期:2011 年3月24日;修回日期:2011 年5月25 日;录用日期:2011年6月1日 摘 要:本文讨论了两顶点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶 ,如果G 中任意一对不相邻的顶点 u,v满足 3n dudvn k ,则 G中任意一个满足 2 nCn k 的圈 C是可 扩的。这里圈 C的下界是最好可能的。由此进一步得到,如果G中任意一对不相邻的顶点 u,v满足 32 2 du dvn ,则 G是完全圈可扩的。 关键词:顶点的度;完全圈可扩图 1. 前言 本文仅讨论有限、无向、简单图,所使用的记号 和术语约定如下,其中未加说明的部分请参照文献 [1]。设 G是一个图,分别表示 G的顶点 集和边集。对及 G的子图H, 令: ,VG EG ,,V GaV G ST : S Na vSvaEG , HVH Na Na, SS vT NT Nv ,, HVH NT NT H VH称为 H的阶。 G Na 叫做顶点 a的度, 记为,在不致误解时也简记为 。 G da da G 表 示G中顶点的最小度。G的由 S导出的子图记为 GS C 。 经过图 G每个顶点恰好一次的圈叫 G的Hamilton 圈。设 C是G的一个非Hamilton 圈,如果 G中存在 圈 ,使 VC VC , 1VC VC ,则称 圈C是可扩的, C 称为 C的一个扩圈.如果图 G中 任意一个非 Hamilton 圈都是可扩的,则称图 G是圈可 扩的。如果图 G的每个顶点都在长度为 3的圈上,并 且G是圈可扩的,则称图是完全圈可扩的。 所有涉及图的路、圈性质的度型充分条件在某种 意义下都源自于下面两个结果。 定理 1[2] 设图G的阶 ,如果 3n 2 n G ,则 G有Hamilton圈。 王江鲁 等图的度和与扩圈65 | 定理 2[3] 设图G的阶 ,如果G中任意一对 不相邻的顶点u,v 满足 3n dv ndu ,则 G有 Hamilton 圈。 1990 年,Hendry 发现已有的一些保证Hamilton 圈存在的度型充分条件实际上隐含着圈可扩性,并得 到了如下结果。 定理 3[4] 设图G的阶 ,如果 3n 1 2 n G , 则G是完全圈可扩的。 下边的定理是本文要证明的主要结果。 定理 4 设图 G的阶,如 果中任意一对不 相邻的顶点 u,v满足 3n G duv nd k ,则 G 1k 中任意一个满足 1 2 nCn k 的圈 C是可扩的。 设 12 1 , mkm GKG Km 3 2 是两个无公共顶 点的完全图,它们的顶点集合分别为 112 ,,, m VG vv v, 212 1 ,,, km VGww w 。 用符号 表示其顶点集和边集分别为 1 GG 121 2 VG GVGVG 121 2 2 ,, ,,:1,2,, iiimi imiikmi EG GEGEG vw vwvwvwim 的图。此图是 阶图,任意一对不相邻的顶 点u,v 满足 ,但其中存在长度为 2nk m du dvn k 2 nm k 的不可扩圈.此例说明定理 4条件中,C的 下界“ 1 2 n k”是最好可能的。 2. 定理 4证明 以下是定理 4的证明。 由定理条件易知 G是连通的.对G的非Hamilton 圈,用表示 C的路 ,用 分别表示 C上的点 12 1m Cvv vv , ll ii vv ji Cvv 1ii j vv v il v 和,v也分别记 成 和 (这里点的下标均模 m)。令 il v 11 , ii v i v i v RVG VC,, C TNR ,:,ERTxyxRyT 。 显然 RT 。 以下总假定 C不是可扩的。 论断 1 x R ,使 。 || C Nx2 证明 假设 x R ,都有 。 || C Nx1 如果 y VC ,使 R Ny ,则 C dyd y。 取 x R ,则 x yEG,且 111 1 RCC dxdyNxN xNy RCn 此矛盾说明 y VC , R Ny 。 注意到 x R , 1 C Nx,所以 12 2 ,1 y yV y Cy ,有 12RR Ny Ny 。并 且 y VC , x R ,使 x yEG(否则,注意到C 不可扩,可得 R Ny ,与上述矛盾)。 由上边的证明可知, 12 ,,, R RR Nv NvNvm 均非空,且两两互不相交.取 y VC,使 VC|()|min: RR NyNv v,则 1 m Ri R i RNvmNy , 所以 2 11 Rn k RnC nn Ny k mCC 1 取 x R ,使 x yEG,则 RC RC dxdyN xN xNyNy 11 11RkCRCknk . 得矛盾.论断 1证完. 论断 2 设 12121 2 ,,;,, x yxyERT x RyyTyy 令 12 12 11 : yCy yCy NyuuNy , 21 21 11 : yCy yCy NyuuNy , 12 12 11 : yCy yCy NyuuNy , 21 21 11 : yCy yCy NyuuNy , 则有 (1) 12 12 yCy NyNy 21 12 yCy NyNy (2) 12 12 yCy NyNy 21 12 yCy NyNy 证明 否则,易得 C的扩圈。论断 2证完。 Copyright © 2011 Hanspub PM 王江鲁 等图的度和与扩圈 66 | 在R中取满足 02 C Nx的点 (论断1保证其 存在性).设 0 x 01 , x yERT,则 10 2 CR C NNy Nx。 在 中取 1CR NNy 2 yy 1 ,使 12 1R yCy NNy , 则 ,且(否则易得 C的 扩圈)。由论断2(1 ), 211 ,yyy 12 yy EG 12 12C yCy NyNy 21 12C yCy NyNy 。 又 12 1 yCy Ny 21 11 yCy Nyy , 2 y 12 1 yCy Ny 21 12C yCy NyNy 。 所以 12 1 yCy Ny 21 12C yCy NyNy C。 (1) 考虑 1R Ny 。 情况 1 1RR Ny Ny 1 (2) 由的取法可知 2 y 12RR Ny Ny , 所以 12RR Ny Ny R.注意到(1)、(2)及 12 1 yCy Ny 12 1 yCy Ny , 21 1 yCy Ny 21 1 yCy Ny , 得下述矛盾 12 11 2 RC RC dy dy Ny NyNyNy 2 1R Ny 12 21 11 yCyy Cy NyNy 22RC Ny Ny 12RR Ny Ny 12 1 (yCy Ny 21 1 yCy Ny 2C Ny CRn 情况 2 1RR Ny Ny 1 (3) 若 12RR Ny Ny ,则 12RR Ny NyR 。结合(1)得 12 11 22 RC RC dy dy Ny NyNyNy 12RR Ny Ny 12 1 yCy Ny 21 1 yCy Ny 2C Ny 12RR Ny Ny 12 1 yCy Ny 21 1 yCy Ny 2C Ny CRn 。 此矛盾说明 12RR Ny Ny ,由此可知 12 CR NNy 。 令,则(3)即 11 yz 11RR Nz Nz 。由上述 证明可知 12 CR NNz |。在 1CR NNz 1 中取 2 zz ,使 21 1R zCz NNz ,则 211 ,zzz 且 12 zz EG (否则易得 C的扩圈)。由论断 2(2), 12 12C zCz NzNz 21 12C zCz NzNz 。 又 12 1 zCz Nz 21 11 zCz Nz z , 12 21 zCz zNz 21 12C zCz NzNz 。 所以 12 1 zCz Nz 21 12C zCz NzNzC (4) 由的取法可得 2 z 12RR NzNz ,所以 12RR Nz NzR 。再注意 到(3)、(4)及 12 1 zCz Nz 12 1 zCz Nz , 21 1 zCz Nz 21 1 zCz Nz , 得下述矛盾 12 11 2 RC RC dzdz Nz NzNz Nz 2 12RR NzNz 12 1 zCz Nz 21 1 zCz Nz 2C Nz 12RR Nz Nz 12 1 zCz Nz 21 1 zCz Nz 2C Nz CRn。 Copyright © 2011 Hanspub PM 王江鲁 等 | 图的度和与扩圈 Copyright © 2011 Hanspub PM 67 情况 2 uVG , 。 2du n定理 4证完。 此时对 vVG,必存在 wVG,使 推论 设图 G的阶,如果 G中任意一对不相 邻的顶点u,v 满足 3n vwE G。所以 32 2 dv dwn , 32 2 du dvn, 得 33 22 22 n dvndw nn 2 2 。于 则G是完全圈可扩的。这里的下界 32 2n是最好 是G中任意两顶点必有公共邻点。取 vyE G,设 v,y 的公共邻点是x,则 v在3圈 上. vxyv 可能的。 证明 因为满足推论条件的3阶图只有完全图 ,此时推论显然成立。以下设。 3 K4n 推论证完。 3. 致谢 因为 G中任意一对不相邻的顶点 u,v 满足 32 2 dudvnn k,这里 2 2 n k。由定理 4,G中任意一个满足31 2 nCn k 的圈 C是 感谢山东省高等学校科技计划项目和山东科技大 学“春蕾计划”项目的资助,亦对本文参 考文献的所有 作者表示诚挚的谢意。 可扩的。下面只需要证明G的每个顶点都在长度为 3 的圈上。 参考文献 (References) [1] J. A. Bondy,U. S. R. Murty. Graph theory with applications. New York: Macmillan London and Elsevier, 1976. 由定理 2,G是2-连通的,所以 2 。 [2] G.A. Dirac. Some theorems on abstract graphs. Proceedings London Mathematical Society, 1952, s3-2(1): 69-81. 情况 1 ,使 。 uVG 1du n [3] O. Ore. Note on Hamilton circuits. The American Mathematical Monthly, 1960, 67: 55. 此时 G中任意一顶点均与u相邻.对 vVG E G , 若,取,则 ,可知 v在3圈上。若 uv wNv u vuwv v ,uvuw u ,任取 G的一条边 x yx vy ,vxvyEG,则 ,可知 v在3圈 vxy v 上。 [4] G. R. T. Hendry. Extending cycles in graphs. Discrete Mathe- matics, 1990, 85(1): 59-72. |