论文部分内容阅读
文研究的图是简单图G,限于本文的使用,记Fan=min{max{d(x),d(y)}|d(x,y)=2}.an定理[1] 2连通n阶图G,Fan≥n/2,则G是哈密尔顿图(H图).证明假设G不是H图.记G的一最长圈为Cm:X1X2…XmX1,因G是2连通的,记Xi,Xj为和G-Cm的一分支G1中y1,y2相邻的两点,且满足{Xi+1,Xi+2,…,Xj-1}中没有点和G1中点相邻.情况1 d(y1)<n/2,且d(y2)<n/2.此时由Fan≥n/2,知d(Xi+1)≥n/2,d(Xj-1)≥