一類圖的哈密頓分類

唐干武,王敏

(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