一类图的哈密顿分类

唐干武,王敏

(1.桂林师范高等专科学校数学与计算机科学系,广西桂林 541001; 2.烟台大学数学与信息科学系,山东烟台 264005)

一类图的哈密顿分类

唐干武1,王敏2

(1.桂林师范高等专科学校数学与计算机科学系,广西桂林 541001; 2.烟台大学数学与信息科学系,山东烟台 264005)

通过研究图G与CP的包装问题,对边数q≥C2p−1−3的简单图进行分类,得到了满足此条件的全部非哈密顿图,由此推广了Ore和Bondy提出的关于此类问题的结果.

哈密顿图;包装;Rs,n图

1 引言及基本概念

2 主要结果及其证明

定理2.1Rs,n是非哈密顿图.

[1]Bondy J A,Murty U S R.Graph Theory with Applications[M].London:MacMillan Press,1976.

[2]Bondy J A.Variation on the Hamilton theme theorem canad[J].Math.Bull.,1972,15(2):57-62.

[3]Yap H P.Some Topics in Graph Theory[M].New York:The Press Syndicate of the University of Cambridge, 1986.

[4]H¨aggkvist R A.Note on Hamilton cycles in graphs[J].Annals of Dis.Math.,North-Holland,1985,27(3):233-234.

[5]王敏,方新贵.包装不含K3的(p,p)图对[J].高校应用数学学报,1991,6(2):66-70.

[6]Wang Min,Li Guojun.Packing a tree of order p with a(p,p+1)-graph[J].Journal of Systems Science and Complexity,2003,6(3):122-132.

[7]唐干武,王敏.包装(p,p−2)图和不含K3的(p,p+1)4图[J].江西师范大学学报,2005,29(3):220-223.

[8]Wang Min,Li Guojun.A result of Erd¨os-S´os conjecture[J].Ars Combinatoria,2000,55:123-127.

[9]苏本堂,和乐亮,孟宪勇.独立数与最小度和[a,b]-因子[J].纯粹数学与应用数学,2008,24(2):289-291.

[10]唐干武,唐高华,王敏.关于边数q≥C2p−1−2的(p,q)图的泛圈性研究[J].广西科学,2007,14(3):206-208.

A Hamilton classfication of some graphs

TANG Gan-wu1,WANG Min2
(1.Department of Mathematics and Computer Science,Guilin Normal College,Guilin541001,China;
2.Department of Mathematics and Information Science,Yantai University,Yantai264005,China)

In this paper,by the study of backing graphs G and Cp,a Hamilton classfication of simple graphs with q≥C−3 is given and all of nonhamilton graphs satisfy above condition are obtained.It further extends the result that Ore and Bondy have got.

Hamiltonian graph,packing,Rs,n-graph

O157.5

A

1008-5513(2009)04-0711-05

2008-05-07.

广西教育厅基金(200807MS032).

唐干武(1962-),副教授,研究方向：图论及其应用.

2000MSC:O5C10