图的度和与扩圈 Extending Cycles and Degree Sums in Graphs

doi:10.12677/pm.2011.12014

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

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/)

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

3n









dudvn k



for each pair of nonadjacent

vertices u,v in , then every cycle C of G with



VG 2

kCn



 is extendable. By the result, we have that

 

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满足

3n







dudvn k



，则 G中任意一个满足 2

nCn

k

的圈 C是可

扩的。这里圈 C的下界是最好可能的。由此进一步得到，如果G中任意一对不相邻的顶点 u,v满足

 

du dvn

，则 G是完全圈可扩的。

关键词：顶点的度；完全圈可扩图

1. 前言

本文仅讨论有限、无向、简单图，所使用的记号

和术语约定如下，其中未加说明的部分请参照文献

[1]。设 G是一个图，分别表示 G的顶点

集和边集。对及 G的子图H，

令：

 

,VG EG

 

,,V GaV G



 



Na vSvaEG ,







HVH

Na Na,

 

NT Nv



,,



HVH

NT NT



VH称为 H的阶。



叫做顶点 a的度，

记为，在不致误解时也简记为。









表

示G中顶点的最小度。G的由 S导出的子图记为





。

经过图 G每个顶点恰好一次的圈叫 G的Hamilton

圈。设 C是G的一个非Hamilton 圈，如果 G中存在

圈



，使









VC VC



，

 

1VC VC

，则称

圈C是可扩的， C



称为 C的一个扩圈．如果图 G中

任意一个非 Hamilton 圈都是可扩的，则称图 G是圈可

扩的。如果图 G的每个顶点都在长度为 3的圈上，并

且G是圈可扩的，则称图是完全圈可扩的。

所有涉及图的路、圈性质的度型充分条件在某种

意义下都源自于下面两个结果。

定理 1[2] 设图G的阶，如果

3n





，则

G有Hamilton圈。

王江鲁等图的度和与扩圈65

定理 2[3] 设图G的阶，如果G中任意一对

不相邻的顶点u,v 满足

3n





dv ndu ，则 G有

Hamilton 圈。

1990 年，Hendry 发现已有的一些保证Hamilton

圈存在的度型充分条件实际上隐含着圈可扩性，并得

到了如下结果。

定理 3[4] 设图G的阶，如果

3n







，

则G是完全圈可扩的。

下边的定理是本文要证明的主要结果。

定理 4 设图 G的阶，如果中任意一对不

相邻的顶点 u,v满足

3n







duv nd k ，则 G



1k

中任意一个满足 1

nCn

k 

的圈 C是可扩的。

设







mkm

GKG Km



 3





是两个无公共顶

点的完全图，它们的顶点集合分别为





112

,,,

VG vv v，





212 1

,,,

VGww w

。

用符号表示其顶点集和边集分别为

GG



121 2

VG GVGVG





121 2

,, ,,:1,2,,

iiimi imiikmi

EG GEGEG

vw vwvwvwim

 







的图。此图是阶图，任意一对不相邻的顶

点u,v 满足，但其中存在长度为



2nk m

 

du dvn k

k

的不可扩圈．此例说明定理 4条件中，C的

下界“ 1



k”是最好可能的。

2. 定理 4证明

以下是定理 4的证明。

由定理条件易知 G是连通的．对G的非Hamilton

圈,用表示 C的路 ,用

分别表示 C上的点

12 1m

Cvv vv



ji Cvv 1ii j

vv v





和,v也分别记

成和 (这里点的下标均模 m)。令

v



v

v

 

RVG VC,，



TNR



,:,ERTxyxRyT



。

显然 RT



。

以下总假定 C不是可扩的。

论断 1



，使。



Nx2

证明假设



，都有。



Nx1

如果





VC ，使





，则







dyd y。

取



，则





yEG，且











 



111 1

RCC

dxdyNxN xNy

RCn

 



此矛盾说明





VC ，





。

注意到



，





Nx，所以









12 2

yV y Cy ，有









12RR

Ny Ny





。并

且





VC ,



，使



yEG(否则，注意到C

不可扩，可得











，与上述矛盾)。

由上边的证明可知，

 





,,,

Nv NvNvm

均非空，且两两互不相交．取





VC，使

 





VC|()|min:

NyNv v，则



Ri R

RNvmNy





,

所以



RnC nn

Ny k

mCC 

1





取



，使





yEG，则

 





 



RC RC

dxdyN xN xNyNy  













11 11RkCRCknk



 .

得矛盾．论断 1证完．

论断 2 设









12121 2

,,;,,

yxyERT x RyyTyy

令









12 12

yCy yCy

NyuuNy



 

 ,









21 21

yCy yCy

NyuuNy



 

 ,









12 12

yCy yCy

NyuuNy



 

 ,









21 21

yCy yCy

NyuuNy



 

 ,

则有

(1)









12 12

yCy

NyNy





 









21 12

yCy

NyNy



 



(2)









12 12

yCy

NyNy





 









21 12

yCy

NyNy



 



证明否则，易得 C的扩圈。论断 2证完。

王江鲁等图的度和与扩圈

66 |

在R中取满足



Nx的点 (论断1保证其

存在性)．设





01 ,

yERT，则



CR C

NNy Nx。

在中取



1CR

NNy 2



，使



12 1R

yCy

NNy



 ，

则，且(否则易得 C的

扩圈)。由论断2(1 )，



211

,yyy









yy EG





 

12 12C

yCy

NyNy





 









21 12C

yCy

NyNy









。

又



12 1

yCy









21 11

yCy

Nyy





，





12 1

yCy











21 12C

yCy

NyNy











。

所以



12 1

yCy







 

21 12C

yCy

NyNy



 

C。 (1)

考虑



。

情况 1



1RR

Ny Ny

1

(2)

由的取法可知



12RR

Ny Ny



，所以



12RR

Ny Ny







R．注意到(1)、(2)及

12 1

yCy









12 1

yCy





21 1

yCy









21 1

yCy



,

得下述矛盾

 



 



11 2

RC RC

dy dy

Ny NyNyNy



 







Ny

 

12 21

yCyy Cy

NyNy





 

22RC

Ny Ny





 





12RR

Ny Ny







12 1

(yCy







21 1

yCy













CRn

情况 2



1RR

Ny Ny

1

(3)

若

 

12RR

Ny Ny





，则

 

12RR

Ny NyR



。结合(1)得









 







11 22

RC RC

dy dy

Ny NyNyNy



 

















12RR

Ny Ny









12 1

yCy









21 1

yCy























12RR

Ny Ny











12 1

yCy









21 1

yCy











CRn

。

此矛盾说明





12RR

Ny Ny





，由此可知









NNy

。

令，则(3)即



11 yz



11RR

Nz Nz



。由上述

证明可知









NNz |。在







1CR

NNz



中取



，使









21 1R

zCz

NNz



 ，则





211

,zzz





且





zz EG



(否则易得 C的扩圈)。由论断 2(2)，









12 12C

zCz

NzNz





 











21 12C

zCz

NzNz





。

又





12 1

zCz











21 11

zCz

Nz z





，





zCz

zNz



 



 

21 12C

zCz

NzNz





。

所以





12 1

zCz











21 12C

zCz

NzNzC



 

 (4)

由的取法可得



12RR

NzNz



，所以







12RR

Nz NzR



。再注意

到(3)、(4)及





12 1

zCz











12 1

zCz



，





21 1

zCz











21 1

zCz



，

得下述矛盾









 







11 2

RC RC

dzdz

Nz NzNz Nz



 

















12RR

NzNz









12 1

zCz







21 1

zCz



















12RR

Nz Nz











12 1

zCz









21 1

zCz











CRn。

王江鲁等 | 图的度和与扩圈

情况 2





uVG ，。



2du n定理 4证完。

此时对





vVG，必存在





wVG，使推论设图 G的阶，如果 G中任意一对不相

邻的顶点u,v 满足

3n





vwE G。所以

 

dv dwn



，

 

du dvn，得

  

dvndw nn

 

。于

则G是完全圈可扩的。这里的下界 32

2n是最好是G中任意两顶点必有公共邻点。取





vyE G，设

v,y 的公共邻点是x，则 v在3圈上. vxyv

可能的。

证明因为满足推论条件的3阶图只有完全图

，此时推论显然成立。以下设。

K4n

推论证完。

3. 致谢

因为 G中任意一对不相邻的顶点 u,v 满足

 

dudvnn k，这里 2

k。由定理

4，G中任意一个满足31

nCn



的圈 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] Ｇ.Ａ. 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 



，任取 G的一条边



yx vy



,vxvyEG，则，可知 v在3圈



vxy

上。

[4] G. R. T. Hendry. Extending cycles in graphs. Discrete Mathe-

matics, 1990, 85(1): 59-72.