（运筹学与控制论专业论文）关于弱泛圈图的一个充分条件.pdf

硕士学位论文 m a s t e r st h e s j s 摘要 对于h 阶图g ，如果g 含长度是”的圈，则称g 是h a m i l t o n 图。若对任意 整数t ( 3 七胛) r g 都包含长度为七的圈，则称g 是泛圈图。图g 称为弱泛圈 图是指g 包含了每个长为，( g ( g ) i c ( g ) ) 的圈，其中g ( g ) ，c ( g ) 分别是g 的围长与周长。1 9 8 1 年h i g g k v i s t 等人证明了边数p ( g ) 一1 ) + 1 的行阶 h a m i l t o n 图是泛圈图或二部图。1 9 9 7 年b r a n d t 将这定理进行了改进，他证 明了对于胛阶非二部图g ，如果p ( g ) ( 职一1 ) 么+ l ，则g 是弱泛圈图。b r a n d t 同时认为条件还可以减弱，他猜想p ( g ) 2 卜么j - 月+ 5 时，结论同样成立。1 9 9 9 年b 0 1 l o b 6 s 和t h o m a s o n 证明了p ( g ) 卜么j - h + 5 9 的”阶非二部图为弱泛圈 图。本文几乎证明了b r a n d ( s 猜想，本文的结论如下：设g 是 阶非二部图， 如果p ( g ) 卜么j 月+ 1 2 ，则g 为弱泛圈图。 关键词：非二部图；h a m ii t o n 图；圈；弱泛圈图 硕士学住论文 m a s t e r s1 1 i e s i s a b s t r a c t a g r a p hi sh a m i l t o n i a n i fi tc o n t a i n sac y c l eu s i n ga i lv e r t i c e s ，i fa l ln v e r t e x g r a p h gc o n t a i n sac y c l eo f l e n g t h kf o re v e r yks u c h t h a t3 k 、t h e n i t i s c a l l e dp a n c y c l i c ag r a p hgi sc a l l e dw e a k l yp a n c y c l i ci fi tc o n t a i n sc y c l e so f a l l l e n g t h sb e t w e e n i t s g i r t h a n dc i r c u m f e r e n c e i n 1 9 8 1 ，h i t g g k v i s t ，f a u d r e e a n d s c h e l ps t a t e st h a ta h a m i l t o n i a ng r a p ho fo r d e r 门a n ds i z ea tl e a s t ( 订一1 么+ li s w e a k l yp a n c y c l i co rb i p a r t i t e b r a n d ti m p r o v e d t h ea s s e r t i o ni n19 7 7 ，h ep r o v e dt h a t e v e r yn o n - b i p a r t i t eg r a p ho ft h es t a t e do r d e ra n ds i z e i sw e a k l yp a n c y l i c a tt h e s a m e t i m e ，h ec o n j e c t u r e d t h ea 蠡e r t i o nh o l d si nt h e c o n d i t i o n o f 印) b 么j 一船+ 5 i n 1 9 9 9 ，b o l l o b d sa n dt h o m a s o ns h o w e dt h a ta nn v e r t e x n o n - b i p a r t i l eg r a p ho fs i z ea t l e a s t e t g ) b 么 - - n + 5 9 i sw e a k l yp a n c y c t i c i n t h i sp a p e r ，w ea l m o s t p r o v et h ec o n j e c t u r eb ye s t a b l i s h i n gt h ef o l l o w i n gr e s u l t ：l e tg b ea l l o d b i p a r t i t eg r a p ho f o r d e rnw i t ha tl e a s t gi sw e a k l y p a n c y c l i c 印) 坛j n + 1 2 e d g e s ，t h e n k e yw o r d s ：n o n _ b i p a r t i t eg r a p h ：h a m i i t o n i a ng r a p h ；c y c l e ：w e a k 】y p a n c y c l i cg r a p h 硕士学位论文 m a s t e r st h e s i s 关于弱泛圈图的一个充分条件 1 引言 本文考虑的图都是简单图，用e ( g ) 与v ( g ) 分别表示图g 的边集与顶点 集，e ( g ) = l e ( g ) l ，顶点x 的开邻域n ( x ) = y ：y x ( g ) ) ，x 在图g 中的次记为 d 。，( 工) 或d ( x ) ，g 中长度为k 的圈记作k 一圈或c 。对于 阶图g ，如果g 含长 度是”的圈，则称g 是h a m i i t o n 图。若对任一整数( 3 ks ”) ，g 都包含长度 为k 的圈，则称g 是泛圈图。图g 称为弱泛圈图是指g 包含了每个长为 z ( g ( g ) f ( ”一1 ) 么+ 1 ，则( 】是弱泛 硕士学位论文 m a s t e r st h e s i s 更进一步，b r a n d t 认为条件还可以减弱，他提出了下述猜想。 猜想zc s ，：设g 为n 阶非二部图，如果e c g ，l 等j 一甩+ s ，那么g 是弱 泛圈图。 1 9 9 9 年了b o l l o b d s 和t h o m a s o n 证明了一个接近b r a n d t s 猜想的结论。 定虬出，：设c 是删e 部图，如果椰，2 h s 。，那么c 是弱泛圈图。 本文改进了b o l l o b a s 的证明，得到一个更近似于b r a n d t s 猜想的结果。 定理l 4 ：设g 是疗阶非二部图，如果e c e ，一j n + ，2 ，则g 为弱泛 2 已知结论 在本文的证明中要用到以下一些结论，显然在文 4 中将引理1 4 、1 5 的条 件换成e c c ，一j 一以+ t 2 也是成立的，我们将这两个引理合并为引理z 。 引理z m ，引理m 川，：设c 是俐e 部图川e ，h 前 若动e ( g ) ， 使得d ( 口) + d ( 6 ) 月一3 并且v ( g ) 一 口，b 是h a m i l t o n 图，则 g 含( n - 1 ) 一圈。 引理2 2 4 ，引理1 0 ：设g 是2 k + 1 阶非二部图，p ( g ) k2 一k + 1 0 ，如果 存在顶点x v ( g ) ，使得g x 是h a m i l t o n 二部图，则g 是弱泛圈图。 硕士学位论文 m a s t e r st h e s i s 引理2 3 4 ，引理4 ：设g 是2 七+ 2 阶图，u w e ( g ) 且g 一似，w 是h a m i i t o n 平衡二部图，“，w 均只与g 恤，w 中同一部类相邻且在这部类至少有一个邻 点，若p ( g ) 2 十4 ，则g 含( 2 k + 1 ) 一圈。 引理2 4 5 ：令g 是n 阶图，c 是g 中最长的圈，c 的长度是c ，则g 的 边数满足p ( g ) 墨e ( g 【矿( c ) ) + ! ! 竺三旦 引理2 5 1 6 ：设g 是 阶图，c 是g 的周长，如果p ( g ) 塑翌型，那 4 么g 是弱泛圈图。 引理2 6 1 7 ：设c = 0 , 2 ，3 n ，1 ) 是图g 的h a m i l t o n 圈，如果d ( 1 ) + d ( h ) ” 且g 7 6 # ( n - 1 ) 一圈，则有d ( h 一2 ) ，d ( n 1 ) ，d ( 2 ) ，d ( 3 ) l 半卜叫m 这样就有d ( z ) 导一1 。因此我们定义图g 中满足d ( x ) 昙i 的点x 为低次点， d ( x ) 詈一l 的点x 为高次点。为了便于讨论，我们对定理1 4 中的 也进行限 硕士学位论文 m a s t e r st h e s i s 制柚趣i l ，目此粼阿蝴定引- n + 1 2 _ 墨 ，则g 中存在比c 长的圈，因 此d ( x ) = d ( y ) = _ n - 厂 。注意到x ，y 都不能与圈c 上的相继邻点相邻否则存在 比c 更长的圈。所以x 只能与c 上的点交错相邻，y 办如此，这样g 中存在比c 更长的圈。当月为偶数时，同样分析也可得出矛盾，v 狮i v ( g c ) l 3 。所以 对任意“，v g c ，都存在长为2 的路只，。则在( “、v ) 与圈c 上相继的4 个点 之问，最多只有两条边，若不然与c 为最长圈矛盾。又由于“，v 在g 一( t 中各自 硕士学位论文 m a s t e r st h e s i s 都有( y - - c - - 1 ) 个邻点，并考虑到d ( “) ，d ( v ) _ n - r 2 ，因此有 ”一2 旦；，则j v g c ，使得x v ，e ( g ) 。那么x 与j ，之 间存在一条长是2 的路x v y 。这样圈c 上任意相继4 点，最多只有两条边与 x ，y ) 相连，若不然g 中存在更长的圈。在圈c # 1 - ，x ，y 最多分别与( 一c 一2 ) 个点相 邻，故有： 棚c m 川( j ，) s 等十2 ( n - c - 2 水詈+ 2 ( n - c - 1 ) 由此不等式得c _ 2 n ，另一方面由题设得c 盯一2 厶n - 1 2 ，因此有 硕士学位论文 m a s t e r st h e s i s ( ”一1 8 ) 2 + 1 0 8 - j * , + + u 彳mj = f 4 ，”f + f 彳。一i a ，”n 爿。i = 矿+ d i + ， n n i v ( h ) l d ，+ d 。，由于i 矿( 日) i = n ，因此得出 d + d 川n ，d ，+ z + 2 玎 ( 1 ) 硕士学位论文 m a s t e r st h e s i s 对于一，b ，c s 矿( 日) 及g c 0 u b ) 显然有 爿n b f i 爿n c i + l b n c i lc i + i x i ( 2 ) 由容斥原理 1 4 ，对于4 ，b ，c v ( m ) ，由于陋u b u c l i v ( h ) = 则有 a n 占i i a i + i b i + l c l - i a n q - b 厂、c i + i a n 曰n c l 一一 ( 3 ) 令r = f ：一+ d 2 ”一3 ，如果j ，r 使h 一扛，x 。 含( n 一2 ) 一圈，则引理3 3 已经成立。因此假设对任何i r 都有一b 。工。 不含( ”一2 ) 一圈。设2 r 因h 一扛：， 不含( 一2 ) 一圈，那么a in a 。= k 。注意到a i * n a ，= o ，在( 3 ) 式中取a = a 3 ，b = a 。，c = 髫得 爿3n a 4 d 】+ d 3 + d 4 1 一 又由于笛+ n = 彳；n 4 = o ，奄+ n a 3 = o ，在( 3 ) 中取爿= a 3 ：b = 田，c = 辑+ 得 j a ，n 爿：1 d ，+ d 。+ d ：一” 现在有 n 露1 = 1 爿，n 爿。i ，运用( 2 ) 式并令彳= a 3b = 胃，c ：筒及：o ， 故 a 3n 4 ；f d l + d 2 + 2 d 3 + d 4 2 n - 1 ( 4 ) 由对称性可得： i a 2n 以；l d l + 2 d 2 + d 3 + d 4 2 n - 1 ( j ) 再在( 2 ) 式中取= a 4b = 田，c = m 3x = 屯) ，则有： f a 4n 爿j j d 1 + d 2 + d 3 + 2 d 4 2 n ( 6 ) 7 硕士学位论文 i v l s t e r lst h e s i s 下面分二种情况证明d 。+ d ：+ 或+ d 。皇尝。 ( 7 ) 情况1 ：a 2n a 海a ，n 尽都是空集。 根据( 4 ) 式与( 5 ) 式，我们有： d i + d 2 + 2 d 3 + d 4 曼2 n + 1 ，d 4 + d 3 + 2 d 2 + d l 2 n + 1 。 因此可以得出 3 留i + 矗2 + 以+ d 4 ) 4 n + 2 + 。+ d 4 ) 又因为x ：，x 。仨a ? u 也勘in 盈= x ， ，所以 d + d 。= i a ：i + i a 。i = i 爿u 爿。i + i 爿jn 爿。i 一一i 因而( 7 ) 式成立，即 矗，+ d ：+ 矗。+ 矗；s 三；三 情况2 ：4n a ：与4n 4 至少有一个不是空集。 不妨设a 3 n 奄g 。首先可以断言： 4 7 + n a 3 = 扛2 ，x 。o ( 8 ) 因为若不然，设z ，彳i + n 以，由于爿i + n 以= + n a ，= o ，因而导出 b m ，x ， n a 3 = o 。这样x 2 在一2 ) 一圈x 3 _ x i - 2 x i _ 工，屯上有相继邻点，我 们可将x ：插入到其相继邻点之间得到g 中的( ”一1 ) 一圈，这样将与假设产生 矛盾e 同理x 3 x 。仨e ( g ) ，即x ，茌4 。则且i + u a ，u 鬈矿( 片) 一i x i ，根据( 3 ) 式可以得出： 爿；n 坞i i 一? + i + l a ，i + i 一+ i i a ：+ n a ，j l 爿i + u 4u 彳；| 8 硕士学位论文 m a s t e r st h e s i s 2 d 3 + d 】一2 一( ”- 1 ) = 2 d 3 + d l h 一1 ( 9 ) 情况2 1 ：若一；n a 3 = a 。 根据( 9 ) 式得：d ，+ 2 d 3 十1 。如果4 。n 4 = 彩，则由( 6 ) 式得出 d 1 + d 2 + d 3 + 2 d 4 2 n 因此有 3 p l + d 2 + d 3 + 以) = p 1 + 2 d 3 ) + p l + d 2 + d 3 + 2 d 。) + p 。+ d ：) + p 2 + d 4 ) ( + 1 ) + 2 n 点抑= 5 n + 1 即 ”如”郇莩。 下设x a 4 n 爿：，则f 3 , 4 ，5 。因g 无( 一1 ) 一圈，则x 2 x 。，x 4 x 6 仨e ( g ) ， 并且类似于( 8 ) 的证明我们可以得出z ，x 。，x 2 x 5 e ( g ) 。因此 簟u a 。矿( h ) 一扛，心i 所以 d ：d 。= j 4 ；u 4 。l l 爿；r 、a 4 1 手，故，( 詈r 一4 9 + 2 8 8 。，矛盾。因此引理3 3 的结论正确。 引理。t ：令e 是脚川阶非二部队h c 是c 中长 为2 一1 的圈，口，b v ( g c ) 且a b e ( g ) ，若d ( 口) = 矗( 6 ) = k ，则是g 弱泛圈图 证明：由引理2 8 知，不含c 4 的m 阶图的最大边数为詈( 1 + o 丽) ，而 h - n + 1 2 扣4 4 e - c 3 - 3 脯g 觚。又溉 1 靴z ， 则g 含( n 一1 ) 一圈。 2 硕士学位论文 m a s t e r st h e s i s 假设g 不是弱泛圈图，则存在，( 3 z 2 k 一4 ) ，使得g 不舍( ，+ 2 ) 一圈，我 们在图g 中定义： ，、1 1 x y e ( g ) 2 ( 卜l o , 叫仨e i 孑) 令c = ( 1 ，2 3 2 k 一1 ) ，显然，对于c 上的两点i 与i + ，一定有 e ( a ，f ) + e ( a ，i + f ) 1 否则若e ( a ，f ) + e ( a ，i 十，) = 2 ，那么一定存在( ，+ 2 ) 一圈( 日，i ，i + 1 i + z ，口) 。因此 2 - 1 2 ( k - 1 ) = 2 d 。0 ) = e ( e ( a ，f ) + e ( a ，f + f ) ) j = i 2 k l 所以和式0 0 ，f ) + e 0 ，f + e ) ) 的2 k 一1 项中，仅一项是0 ，其余各项均为1 。在 i 顶点集y ( c ) = 1 ，2 ，2 k 一1 ) 上定义如下一个等价关系 i 与等价曹j 兄z ，使得i 三j + a ( m o d 2 k 一1 ) 。 由于每个等价类中元素个数相同，且j 矿( c ) i = 2 k 一1 ，故每个等价类中有奇数个 元素。因此每个等价类中都存在两点m l ，m + 1 _ l 使得： e ( a ，坍，) + e ( a ，m + 1 ，) = 0 。 故y ( c ) 上只有一个等价类，即有( 7 ，2 k 一1 ) = 1 。因此不妨设口( q f ) + e ( a ，2 f ) = 0 所以得 p 0 ，) = o ，p ( 口，2 z ) = o ，e ( a ，3 ，) = 1 ，p ( d ，4 0 = o ，e ( a ，5 0 = 1 ，e ( a ，( 2 k 一1 ) ，) = 1 ， 这样圈c 上与口点相邻的点集为 3 1 ，5 l ，7 l ( 2 尼一1 ) ( m o d 2 k 一1 ) 。 硕士学位论文 m a s t e r st h e s i s 同样b 点与圈c 上相邻的点集也为 3 ，5 1 ，7 1 ( 2 k 一1 ) ( m o d 2 k 一1 ) 。否则若 b 点与 2 l ，4 l ( 2 一2 ) ) 相邻，那么g 一定为弱泛圈图，矛盾；若b 点与 ，3 l ，5 l ( 2 k 一3 ) l 相邻，由o ，2 k 一1 ) = 1 知，j 使玎；，一l ( m o d 2 k 一】) ，显 然，2 f 2 k 一2 。若 为偶数，e ( a ，o + 1 ) 7 ) = 1 ；若f 为奇数，则p 0 ，( 2 女一f ) ) = 1 。 而p ( 6 ，) = 1 ，两种情形盘，b 均分别与圈c 上长为f - 1 的路的两端点相邻，这样 形成了( ，+ 2 ) 一圈，与假设矛盾。 当日与6 在圈f 上有相同的邻点时，若f 为偶数且r 2 k 一2 时，由 e ( a ，3 ，) = 1 - 与e ( b ，口+ 3 ) ，) = 1 可得( ，+ 2 ) 一圈，矛盾。若，为奇数，由p ( 口，3 1 ) ：】及 e 0 ，( 2 + 2 一t ) t ) = 1 也可得到( ，+ 2 ) 一圈，叉产生矛盾。如果f = 2 k 一2 即 ( 2 k 一2 ) = ，一1 或2 7 1 = o ( m o d 2 k 1 ) 时，则有，：k ，那么圈c 上与d 及6 相 邻的点集为扯+ 1 ，女+ 2 ，k + 3 2 k 一1 ，若点集 1 , 2 女 中，除属于圈c 上的边 外，还有边相邻或者与点集 k + 1 ，k + 2 2 k i ) 中有边相邻( 除f 上的边外) ， 则 占一定为弱泛圈图， 这样与假设矛盾。否则 e ( g ) ( ：+ 1 + k - l = 生二吾生呈，与已知e ( g ) 女z 一女+ 1 1 矛盾。故引理得证。 4 定理1 4 的证明 我们首先限定定理1 4 中的最小次占( g ) 2 。因为若占( 6 ) 1 ，令 m c g 啪一仍黼二部图且耶叫l 学2 卜枷棚 硕士学位论文 m a s t e r st h e s i s 纳假设可以得到g 是弱泛圈图，下面用归纳法证明定理1 4 。 证明：( i ) 当周长c ( g ) 月一1 时，再g 中取长为( n 1 ) 的圈因为若 e ( g ) = ，由引理3 3 及引理2 1 得出g 一定含一1 ) 一圈。令x g c ，若x 是低次点且g x 不是二部图，则由归纳假设知g x 是弱泛圈图，因而g 也是 弱泛圈图。若并是低次点且g z 为二部图，则伽一1 ) 为偶数，故肝为奇数。令 1 7 = 2 + 1 ，显然e ( g ) 2 2 一k + 1 0 ，由引理2 2 可得g 是弱泛圈图。 如果x g c 是高次点，当n = 2 k + 2 或h = 2 k + 1 ，并且d ( x ) + 1 时，则 对vl ( 3 zs h ) ，3 i 使得x ，】：，+ f 一2 ( x ) 这样g 含长为j 的圈姒，x x i + l - 2 x ， 此时g 为泛圈图，因此以下仅考虑h = 2 k + 1 时，d ( x ) = 的情况。 ( a ) 如果x 与f 上的点交错相邻，则f 上一定有一条偶弦，否则占为二 部图，而此时g 中一定存在每个长为，( 3 z ”) 的圈，则g 为弱泛圈图。 ( b ) 如果工与f 上的点不交错相邻，那么g 一定含有长为( 2 k 一1 ) 的圈d ， 若假设g 不含( 2 k 1 ) 一圈。令c = ( 1 ，2 ，3 2 k ) ，显然 e ( x ，f ) + e ( x ，i + 3 ) 1 ， 由于 2 d ( x ) = 2 k = ( e ( x ，f ) + e ( x ，f + 3 ) ) ， 故对任意i 都有 e ( x ，f ) + e ( x ，f + 3 ) = 1 。 由敏( x ) ：掣以及工与f 上的点不交错相邻可知，x 在f 上一定有相继邻点。 不妨设 1 ，2 ( ( x ) ，由于p ( x ，2 a ) + e ( x ，3 ) = 1 ，不妨设p ( x ，3 ) = 1 ，易知 硕士学位论文 m a s t e r st h e s i s ( x ) = 1 ，2 ，3 ，7 ，8 ，9 2 k 一5 , 2 k 一4 , 2 k 一3 ) 并且6 】2 k 。 令丙( x ) = 矿( c ) 一v ( x ) 。如果对所有f - n ( x ) 都有d ( f ) = 2 ，则 d ) + 2 k + k ( k + 1 ) 。 y e l 7 】 所以2 2 一互女+ 2 2 2 e ( g ) k + 2 k + k ( k + 1 ) ，矛盾。因此存在i 丙( x ) ，使 d ( i 1 3 。 下设f e ( c ) ，其中j f 1 ，我们将构造存在g 中的( 2 一1 ) 一圈。显然如 果，= i + - 2 t g 中有( 2 k - 1 ) 一圈。t i 殳l ；- j l 3 如果，+ l ( x ) ，则因为i + 3 | ( x ) j 那么g 中存在( 2 一1 ) 一圈 ( x ，i + 3 ，i + 4 ，i ，i l - ，十l ，x ) 。同理一1 n ( x ) 时，因为f 一3 n ( x ) ，贝0g 中存在( 2 k 一1 ) 一圈( x ，f 一3 ，i 一4 ，i ，f + 1 - 一1 ，x 。 若+ 1 仨( x ) ，j 一1g v ( x ) 。由j 一1 壁( x ) 得出：j 2 ，3 ，4 ( m o d 6 ) ，由 + 1 茌( 工) 得：，1 , 2 ，0 ( m o d 6 ) ，所以；5 ( r o o d 6 ) 。此时 - ，一2 ，j + 2 0 ) 。 又 f _ 2 ，i + 2 n n ( x ) o ，不妨设i 一2 | v ( x ) ，则g 含( 2 k 一1 ) 一圉 ( x ，i 一2 ，i 一3 i ，i + 1 j 一2 ，x ) 。综上得出g 中含有长为( 2 女一1 ) 的奇圈。 由于g 含长为( 2k 1 ) 的奇圈d ，令x ，y g - d ，当x 为低次点时，因为 d c g x ，则g x 为非二部图，由归纳假设g z 为弱泛圈图可知，g 也是弱泛 圈图。当d ( z ) k 时，若d 。0 ) k l ，此时g 为弱泛圈图，若d ( x ) = d ( y ) = k 且x y e ( g ) ，由引理3 4 知g 也是弱泛圈图。 1 6 硕士擎位论文 m a s t e r st h e s i s ( i i ) 当周长c ( g ) 一2 时，+ l c l = c ( g ) = c ，若p ( g ) 掣，由引 舭油c 朋泛熙如果引眺酾，掣，蚓酗，得 c 外有一个低次点x 。若g x 仍为非二部图，由归纳假设g x 是弱泛圈图，g 也是弱泛圈图。故可假定g x 是二部图，由此，c 是偶圈。 当g x 是二部图时，如果圈c 外除x 外再无低次点，则由引理3 2 知 i c f ：m 一2 且另一点y g c 是高次点，即d ( y ) _ n - - 1 。若砂e ( g ) ，g 显然 是弱泛圈图；若叫e ( g ) ，由g x 是二部图，则y 与c 上点交错相连，而 d ( g ) 2 ，x 也一定与y 在c 上相邻的点相邻，这样g 也是弱泛圈图。如果还 有一点y g c 是低次点，同理g y 也是二部圈。故g x y 是二部图，此时 有 哪一圯h m z 印 ( 兰- 2 ) 唾_ 2 由此可得g - x y 要么连通，要么有两个分支，其中一个分支是孤立点。 情况l ：g x y 有两个分支，其中一个分支是孤立点虮， 因占( g ) 2 且c ，则“仅与x 及j ，相邻。此外，x 与g 一 x ，y ，“】中的一 个部类相邻，否则g - y 不是二部圈，y 亦如此。如果x 及y 与g 一 x ，y ， 中同 一部类相邻，则- d e ( 0 ) ，否则g 为二部圈。这样g 一“就是非二部图，出归 纳假设g - u 是弱泛圈图，g 也是弱泛圈图。如果x 及y 与g 一 x ，j ，n 叫，的不同 硕士拳位论文 m a s t e r st h e s i s 部类相邻，则将恤，y ，“) 收缩成一点w 后构成一个新图g ， 邸胁c 即， l 华卜咽m l 4 j 由归纳假设g 。是弱泛圈图。由cc g 。，则g 含( i c l 1 ) - 圈。然而g - 扛，y ，“ 所 含的圈皆为偶圈。故长为( i c l - 1 ) 的奇圈一定包含了点。因此g 包含长为 n c 卜1 ) 的圈。与c 为最长圈矛盾。 情况2 ：g x y 是连通图。 x 劢必定只与g z y 中的同一部类相邻且x y e ( g ) ，否则占是二部图。 同时我们还可以断定y 是x 在二部图g x 中y 所在类的唯一邻点，若不然 g y 不是二部图。这样在圈f 外不可能有三个低次点芏，y ，z ，否则z 是二部图 g x 中：所在类的x 的唯一邻点，故d ( x ) = 2 ，同理，d ( y ) = d ( ：) = 2 。则x _ v = 三个点构成了g 的一个三角形分支，与g 连通矛盾。因而g c 中最多有2 个 低次点，由引理3 2 ，在g c 中最多由一个高次点，因此圈c 外最多有3 个 点。由f 为偶圈，则n = 2 k 十1 时， c l = 2 k 一2 ；”= 2 k + 2 时，1 c 1 = 2 k 。 情况2 1 ：当月= 2 k + l ，蚓= 2 k - 2 时。令g x 为二部图g ( _ ，) 。如果 i k l = + 1 ， k i = k - 1 ，则阢y ( c ) i = 2 。由引理3 2 ，在k 矿( c ) 中必有一个 低次点y ，x y 是x 在二部图g f 工中y 所在类的唯一邻点。由于f 外不可能有三个 低次点，则k ，( f ) 中另一点“为高次点，故d ( “) 。然而i l = k 一1 ，则“ 定与x 相邻。与y 是x 的唯一邻点矛盾a 若附j = i 屹l = k ，令 y ) = u y ( c ) ， 硕士学位论文 m a s t e r st h e s i s z ) = k 矿( c ) 。若x y e ( g ) ，则d ( y ) k ，故y 与中所有点相邻。设 y + n 。i ( x ) n c ，在f 上将y 。用y 取代得到最长圈c ，则x 仍为g 的低次点 墨y ，= 5 g c ，显然( x ) 略( x ) 矛盾。因此砂e ( g ) ，同理，x z ( g ) 。 在g 中将 x ，y ，：) 收缩成一点w 并去掉与z 相邻的边后构成一个新图g ，则 e ( 0 1 ) = p ( g ) 一a ( x ) 且g 是非二部图，由归纳假设g 是弱泛圈图，因此g 含 ( i c 卜1 ) 圈，那么g 含长为( i c i + 1 ) 的圈，矛盾。 情况2 2 ：当”= 2 k + 2 ，1 c 1 = 2 k 时。令g x 为二部图g ( k ，v 2 ) 。其中 l u i = k + 1 ，l 屹i = k 。令k c = y ) ，若y 为高次点，即d ( y ) k 十1 ，则x y e ( g ) 并且( ( ) = k 。设“是工在k 中的任一邻点，则“己“一y x u 是g 中长为( t e l + 1 ) 的圈，矛盾。若y 为低次点，则y 是二部图g x 中y 所在类的x 的唯一邻点， 由引理2 3 可得g 含( 2 k + 1 ) 一圈，与c 为最长圈矛盾。证毕。 9 硕士学位论文 m a s t e r st h e s i s 参考文献 1 】b o n d yj h ，m u r t yu s r ，g r a p ht h e o r y w i t ha p p l ic a t i o n ，l o n d o n ：t h e m a c m i1 1 a n p r e ss 19 7 6 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 【1 幻 1 5 1 6 】7 j ，a b o n d y ，p a n c y c l i cg r a p h s ，j c o m b i nt h e o r y s e r b1 1 ( 1 9 7 1 ) 8 0 一8 4 s t e p h a nb r a n d t ，a s u f f i c i e n tc o n d i t i o nf o ra 1 1s h o r t c y c l e s ， d i s c r e t ea p p l i e db a t h s7 9 ( 1 9 9 7 ) 6 3 6 6 b b o l l o b d s ，a t h o m a s o n ，w e a k l yp a n c y c l i cg r a p h s ，j c o m b i nt h e o r y s e rb7 7 ( 1 9 9 9 ) 1 2 1 一1 3 7 j ，a b o n d y ，l a r g ec y c l e si ng r a p h s