（运筹学与控制论专业论文）关于图的几类控制数的界.pdf

硕士学位论丈 m a s t e r s t h e s i s 并且若1 ) ， 则有 7 , ( g ) ? ( b +2 一2 r ) n / ( b +2 +2 r ) . 对于任意图g ,n =i v ( g ) i , b . =6(g),-aa=0 ( g ) ， 若=2 r + 1 ( r e n , r 1 ) , 则有 7 3 ( g ) _ ( b +3 一 ) n / ( b +1 + ) 并证明了在b 3 时， 本文的下界优于5 中 的下界 同时给出了上述定理中 一些可达下界的图类， 特别， 本文门讨论了二分图的符号控制数与参数b 的关系. 得到了下述结论: 若g二( x , y , e ) 为n阶二分图，b =b ( g ) ， 则 7 , ( g ) _ 2 r j 4 ( b . + 2 ) n + ( j - + 2 ) 2 一 ( b + 2 ) 1 / 2 1 一 。 对于图的最大次较小的符号控制数的下界【 7 中 进行了研究. 本文在此基础上 进一步给出了一系列充分条件的命题.同时给出了上述定理中一些可达下界的图 类. 对于连通图的强控制数的上界图中 提出了 一个 猜想， 设图g为二 阶的 连通图 的，b =b ( g ) ， 则有 7 s t ( g ) 1 .t h e p一d o m i n a t i o n n u m b e r o f a g r a p h i s d e fi n e d t o b e t h e i n fi m u m o f 二 ( f ) t a k e n o v e r a l l p一d o m i n a t i n g f u n c t i o n s f , w h e r e w ( f ) =f ( 1 1 ) =e v e v f ( v ) .wh e n p= 0 , 1 ) w e o b t a i n t h e s t a n d a r d d o m i n a t i o n n u m b e r . wh e n p= 0 , 1 ,p= 一 1 , 0 , 1 ,p= 一 1 , 1 w e o b t a i n t h e f r a c t i o n a l , m i n u s o r s i g n e d d o m i n a t i o n n u m b e r .a t t h e e ig h - t e e n e h s o u t h e a s t e r n i n t e r n a t i o n a l c o n f e r e n c e c o m b i n a t o r i c s , g r a p h y t h e o r y a n d c o i n p u t i n g , s .t .he d e t n i e n a i f o r m a l l y d e fi n e d f r a t i o n a l d o m i n a t i o n . r e c e n t l y ,t h e i d e a o f a l l o w i n g n e g a t i v e w e i g h t s w a s p u t f o r w a r d ,i . e . m i n u s o r s i g n e d d o m i n a t i o n n u m b e r . i n t h i s p a p e r ,w e s u r v e y s o m e r e s u l t s c o n c e r n i n g t h e b o u n d s o f s i g n e d d o m i n a - t i o n n u m b e r i n a n a r b i t r a y g r a p h a n d t h e s t r o n g d o m i n a t i o n n u m b e r i n a c o n n e c t e d g r a p h , n o r d h a u s - g r a d d u m b o u n d s o f t h e t o t a l d o m i n a t i o n n u m b e r a n d t h e c o n - n e t t e d d o mi n a t i o n n u mb e r . t h e l o w e r b o u n d s o f s i g n e d d o m i n a t io n n u m b e r h a v e b e e n s t u d i e d i n 5 1 .i n t h i s p a p e r w e d o f u r t h e r r e s e a r c h a n d o b t a i n s o m e n e w l o w e r b o u n d s o f s i g n e d d o mi n a t i o n n u m b e r o f a g r a p h r e p r e s e n t e d b y t h e n e w p a r a m e t e r b . f o r a g r a p h g o f o r d e r n ,b =b ( g ) , t h e n 7 8 ( g ) ? 2 r ( j b . 2 + 8 ( 6 - + 2 ) - ) / 4 1 一 n . i i i 硕士学位论文 m a s t e r s t h e s i s f o r a g r a p h g o f o r d e r n ，二=ie ( g ) l , a * =b * ( g ) , t h e n 7 , ( g ) n 一 4 r n / 3 ( 干 b * / 2 ) +1 ) f o r a g r a p h g o f o r d e r n , b * 二b * ( g ) , ,=a( g ) , t h e n y ( g ) ? ( b . +2 一a ) n / ( b * +2 + ) . f u r t h u r , i f 1 ) , t h e n 7 8 ( g ) _ ( b * +2 一2 r ) n / ( b * +2 +2 r ) . f o r a g r a p h g o f o r d e r n , b * =b * ( g ) , ,=a ( g ) , i f =2 r +1 ( r n , ， 1 ) , t h e n 7 9 ( g ) ( b * +3 一 ) ,n / ( b . +1 + ) . a n d w e s h o w t h a t t h e s e l o w e r b o u n d s a r e b e t t e r t h a n t h o s e i n 5 i f b - 3 . i n t h e m e a n t i m e , w e g i v e s o m e g r a p h s w h i c h a t t a i n s t h e b o u n d s .i n p a r t i c u l a r , w e o b t a i n t h e l o w e r b o u n d r e p r e s e n t e d勿 t h e n e w p a r a m e t e r b o f s i g n e d d o m i n a t i o n n u m b e r o f a b i p a r t i t e g r a p h . l e t g二( x , i 几 e ) b e a b i p a r t i t e g r a p h o f o r d e r n ,b * =b * ( g ) , t h e n -y y ( g ) _ 2 f j 4 ( b * + 2 ) n + ( b . + 2 ) 2 一( b * + 2 ) 1 / 2 1 一 。 t h e l o w e r b o u n d s i n s m a l l - d e g r e e g r a p h s h a v e b e e n s t u d i e d i n 7 .b a s e d o n t h o s e ,nv e o b t a i n s o m e r e s u l t s a s f o l lo w s .a n d w e g i v e s o m e g r a p h s w h i c h a t t a i n s t h e b o u n d s o n t h e u p p e r b o u n d s o f s t r o n g d o m i n a t i o n n u m b e r , t h e f o l l o w i n g c o n j e c t u r e h a s b e e n p u t f o r w a r d b y 8 二 ，e p r o v e i t t r u e f o r t h e f o l l o w i n g a r s e . a t t h e e n d， m o t i v a t e d 勿 1 0 1 ,w e o b t a i n s o m e n o r d h a u s - g r a d d u m b o u n d s o n t h e t o t a l d o m i n a t i o n n u mb e r a n d t h e c o n n e c t e d d o m i n a t i o n n u m b e r o f a g r a p h . k e y wo r d s : d o m i n a t i o n n u m b e r , s i g n e d d o m i n a t i o n n u m b e r ,t o t a l d o m i n a t i o n n u m b e r c o n n e c t e d d o m i n a t i o n n u m b e r , s t r o n g d o mi n a t i o n n u m b e r , b i p a r t i t e , ma x i m u m d e g r e e , d o ma t i c n u m b e r r v 硕士学位论文 m a s t e r s t i 止 s i s 关于图的几类控制数的界 1引言 图的控制数在图的结构中起着重要的作用. 近年来， 关于这方面的研究有许多 成果. 同时， 随着实际问题的发展， 控制数的种类在不断增加. 虽然许多类的控制数 有很好的应用背景， 但其相应的判定问题是n p完全问题或n p困难问题.因而， 对于控制数的上下界的精确估计是人们感兴趣的一个问题， 它对于设计相应的近似 算法具有实际意义. 控制数的理论有着较长的发展历史 有关控制数的最早的思想萌芽可以追溯到 四百多年以前的印度的一种棋盘的游戏. 后来， 五皇后间题和八皇后问题重新引起 了人们对控制数概念的 兴趣. 这些可在1 9 0 1 年a l t r e r u 。 和1 9 3 6 年k o n i g 的著作中 查到. b e r g e 在1 9 5 8 年和o 、在1 9 6 2 年的有关书籍中， 对于控制数给出了正式 的数学定义. 但是， 在1 9 7 2 年以前， 关于这方面的研究成果不是很多. 然而，自 从 c o c k a y r t 。 和h e d e t n i e r “着手控制数的理论的研究，并在1 9 7 5 年出了一本研究成 果的综述以后， 这种情形就发生了很大的变化. 许多人相继投身于这方面的研究工 作 在1 9 7 7 年 有关文 献只 有2 0 篇.1 9 9 0 年 p ， 即对图g的顶点进行赋权， 若对于 v中任 硕士学位论文 m a s t e r s t he s i s 何一个顶点v ， 我们有f ( nv ) 1 成立. - ( f ) =f ( 1 ) =f - c l f ( v ) ， 我们称 m i n w ( f ) f为图g的一个p 一 控制函数 为图g的p - 控制数.人们最初是在 研究尸二 0 , 1 ) 的 情形， 也就是 我们 通常意义 下的 控制数. 后 来， 在 第十八届东南 组合和图论及计算国际学术大会上，s .t . he d e t n i e 7 n i 定义了分数控制数，也就是 p二 0 , 1 的情形. 直到近几年，人们才把目 光放到p = - 1 , 0 , 1 或尸= - 1 , 1 ) 的情形， 也就是我们所说的负控制数和符号控制数. 本文主要对于符号控制数的下界和连通图的强控制数的上界以及全控制数和连 通控制数的n o r d h a u s - g r a d d u m型界的问题进行了研究. 关于符号控制数的下界，【 5 中 给出了几个其下界的估计. 本文在此基础上进 一步讨论了符号控制数与参数6 的关系，得到了下述几个结论: 定理 1 . 对于任意的， * 阶图民6 =,5 ( g ) ， 则有 ， 、 ( g ) - 2 f ( j 6 * 2 + 8 ( 6 - + 2 ) ) l ) / 4 ) 一 ， ， 定理2 . 对于任意图以n = v ( g ) j , n l = j e ( g ) j , 6 =6 ( g ) ， 则有 y y ( g ) n - 4 1 n / 3 ( f 6 * / 2 +1 ) 定理3 . 对于任意图g ,n = v ( g ) j , 6 =6 ( g ) , ,=a ( g ) ， 有 y 5 ( g ) ( p+2 一 ) 叮( 6 . 十2 + ) . 定理 ? ， n, r 对于任意图g ,? 二! v ( g ) i , 6 =6 ( g ) , ,二 ( g ) ， 若- ( d +2 一2 1 -) n l ( 6 * +2 +2 r ) 定理 ren, r 对于任意图g ,n =i v ( g ) i , p=6 ( g ) , a=0 ( g ) ， 若=2 r +1 1 ) ， 则有 y s ( g ) “ * +3 一 ) n / ( d +1 + ) 并证明了在6 * 3 时， 本文的下界优于同 中的下界. 同时给出了上述定理中 一些可达下界的图类. 特别， 本文门讨论了二分图的符号控制数与参数b 的关系. 得到了下述结论: 定理6若g = ( x, y , e ) 为二阶二分图，6 . = b ( g ) ， 则 % ( ) 2 丫 4 ( p+ 2 ) n + ( a . + 2 ) 2 一必 + 2 ) / 2 卜 ， 对于图的最大次较小的符号控制数的下界 7 中 进行了研究. 本文在此基础上 进一步给出了一系列充分条件的命题: 定理7 . 在 d 2 ， 则有 y 可2 定理8 . 在 n / 5 定理9 . 在 4 d 2 + d 3 + d 4 , 则有 -y , n / 4 . 定理1 0在 2 d 2 + d 3 + d 4 , 则有- y , n / 3 - 定理1 1 . 在_ 4 d 2 + 3 d 3 + 5 d 4 + 3 d 5 , 则有 / j ?可2 . 同时给出了上述定理 7 一 定理 u 一些可达下界的图类. 硕士学位论文 ma s t e r s t hf s i s 对于连通图的强控制数的上界8 中提出了一个猜想， 设图g为n 阶的 连通图 的，b =6 ( g ) ， 则有 7,t(g) 4 ) 阶的连通图，6 二6 ( g ) ， 若6 7 ) 阶的 连 通图 ，6 = 6 ( g ) ， 二二 w( g ) l ， 若 w( g ) j, lb ， 二三( 二 一 4 ) / 3 且6 3 ) 阶的连通图，6 = 6 ( g ) ， 二= b v ( g ) ， 若 w( g ) :a (d ， 且对于所有。 : v w ( g ) ， 有n( u ) u n ( v ) =(p 成立，则有上述猜想 成立. 最后， 在【 1 0 的激励下， 本文讨论了全控制数和连通 控制数的n o r d h a u s - g r a d d u i n 型界的问题. 定理 1 5 . 对于n阶图g ,-y t =7 t ( g ) , d o =d e ( g ) ， 若d t 2 成立，则有: y t +d , 2 成立， 则 7 t + d t = n / 2 +2 当 且仅当7 t =i n / 2 或d t = n / 2 . 定理 1 7 . 对于二阶图g ,y , = y( g ) , d , = d , ( g ) ， 若d , 2 且%2 成立， 则 有: y +d o - 2 . x i 表 示不小 于x 的最小整数. x 1 表 示不 大于x的最大整数. 州 表示集 合x的 基数. 在不 作 说明 的 情况 下，n表 示自 然数集，n o =nu 0 . 有一 些术 语放在相应的章节作特别说明， 其它未提及的术语见叫. 3关于一般图类符号控制数的下界与6 * ( g ) 的关系 3 . 1准备工作 图的 符号控制 数的定义最初由! 1 中 提出 . 定义3 . 1在图g=( ve ) 中， 定义函 数f : - - 1 , 1 ， 令f的 权为 二 ( f ) = e = e v ( g ) f ( x ) ， 对 于v ( g ) 中 的 a x ， 定 义f x = e . e n ，二 f ( n ) ， 此 处 书n x i+ 1 记为x . 图的符号控制函数是指函 数:f : - - - 1 , 1 使得对任意的 x e v ( g ) , f x 1 . 图g的并号控制数定义为 : - mg ) = m i n w ( f ) i f为图g的符号控+ 1 a 数 . 权为y , ( g ) 的符号控制函 数称为 硕士学位论文 ma s t e r s t i i e s i s 图g的一个 %一函数. 定 理3 . 2 1 8 图的并号 控制数的判 定问 题是n p完 全的， 甚至对于二分图或弦图 也是如此. 这个定理表明了确定符号控制数的界是有意义的. 对于树的符号控制数的下界，有下述两个结果: 定理3 . 3刀 了 设t为一个n 2 阶树，则有%( 刀 ( n + 4 ) / 3 ， 等式成立当且仅当 t是一 个具有3 k + 2 恤e n 0 ) 个顶 点的 路. 定 理3 . 4夕 了 设t为一个7 1 全2 阶树，则有%( t ) 全， ( 劝十1 双 t ) 为树t的独立 数 . 对于一般图类符号控制数的界，有下述几个结果: 定 理3 . 5 1 设g为 一 个 a ; 正 则二 阶图 ， 则 有y , ( t ) _ 可( k 十 1 ) . 定 理3 . 6 2 设g为 一 个 k 正 则。 阶图 且k 为 奇 数 ， 则 有y , ( g ) _ 2 7 a / ( k + 1 ) . 定 理3 . 7 2 设g为 一 个 三 正 则。 阶图 ， 则 有y , ( g ) _ n 1 2 . 定 理3 . 8 ( 2 ) 设g为 一 个三 正则二 阶图 ， 则 有% ( g ) _ i ( g ) + l ,i ( g ) 为 图g的 独 立教，且这个界是紧的. 定理3 . 9夕 了 设g为一个二阶图， 其次序列d l d 2 2 k 一n . 对于一般图类符号控制数的下界，! 司中进一步给出了下述结果: 定 理3 . 1 0 5 对二 阶图g ， 有7 ., ( g ) 2 ( 、 l + s r a - 1 ) / 2 ) 一 、 定 理3 . 1 1周 对二阶图g ，二二e ( g ) i， 有%( g ) n - 2 n i / 3 . 定 理3 . 1 2 5 衬。阶n g , 有7 9 ( g ) ? ( 6 ( g ) +2 一 ( g ) ) n / ( 6 ( g ) +2 +0 ( g ) ) . 本节将利用参数d ( g ) 对于上述结果进行全面改进， 在第二小节中给出主要定 理及其证明和相应的可达上界的图.在第三小节中比较下界的大小. 先给出几个引理如下: 6 硕士学位论文 m a s t e r s t i 正 sts 引 理3 . 1 3若s ( g ) 二( d ， 则 必有7 , ( g ) =i ( g ) i 证: 由已 知v ( g ) 二i ( g ) u 5 2 ( g ) u p ( g ) ， 令f为图g的一个% 一 函数. 若 x e i ( g ) ， 则必有f ( x ) =1 . 若x e s 2 ( g ) ， 则必有f ( x ) =1 ， 若不然， 存在x 0 e q ( g ) 使得f ( - 0 ) =一 1 ， 则有f x o _ e :l e h , ( f d ( v ) / 2 1 + 1 ) 其中 p= : c v ( g ) if ( x ) =1 ) , m= 二 v ( g ) if ( 二 ) =一 1 ) 证: 对于 所 有的二 e v ( g ) ， 因 为c , -,e n x p - ) 1 , 我们 有 i n x n p 】 一】 .n :c n m! 全1又由于 i n 川 =: 川n p j +in川n .1 1 卜 d ( x ) +1 , 从而in 【二 n p i d ( 二 ) / 2 +1 ， 即 n x n 1 , 1 d ( 二 ) / 2 1 +1 ， 故 e ( p , a l ) 又in !二 n p i 又( d ( x ) / 2 卜 1 ) xea i 证毕. 引理 3 . 1 5衬。阶图g ， 采用引 理 3 . 1 1, 的记号，有e ( p , a -1 ) ( 6 / 2 1 +1 ) ( i t - 1 ) 证 由 符号控制数的定义和引 理 3 . 1 4 我们可知， 若二e a l ， 则必有二s ， 从而 d ( x ) l 2 干 6 / 2 1 ， 代入引 理 3 . 1 4 中即得.证毕. 3 . 2 主要结果及证明 定理 3 . 1 6对于任意的。阶图g 声 * -6 ( g ) , i l l】 有 y , ( g ) _ 2 ( x / 6 2 +s ( 6 +2 ) n ) / 4 1 一 。 . 证: 采用引理 3 . 1 4 的记 号， 我们有%( g ) = i p i - i n -i ! 二2 p - n . 由引理 3 . 1 5 ,e ( p , d ! ) ( d / 2 干 +1 ) ( 二 一 p ) ， 因 而尸中至少存在一个顶点x使得二 至少与m 中( 厂 p / 2 1 + 1 ) ( 二 一 p ) l p 个顶点相邻. 从而p in同n p i 1 +( b / 2 +1 ) ( n 一 川 /， 即 p 2 + b ; l 2 p 一 ( r 6 % / 2 ) + 1 ) 1a 。 由尹 非负 性， 我们 可 解得，p _ ( 了 b , 2 + 8 ( b + 2 ) , , ) / 4 . 因 此， 7 ( g ) 2 ( 了 a , 2 + 8 ( 8 - + 2 ) n ) / 4 ) 一 ， ， 证毕. 定理 3 . 1 7对于任意图民二=i 1 ( g ) i, 。 =i e ( g ) i , a =p( g ) ， 则有 7 s ( g ) t : 一4 7 n / 3 ( ( b rt / 2 j +1 ) 证 : 考 察图g关 于尸的 导出 子图侧p ， 对 所 有 的t 。 p ， 因f e n 二 f ( u ) 1 ， 有 in( 二 ) n p i in ( v ) n _1 1 成立，从而 艺ch ( x ) 艺in ( ， ) n a i l 二 e ( p , a l ) 根据引理 3 . 1 5 , 2 e ( g p ) ( f p / 2 1 +1 ) ( n 一 p ) . 从而有 二 e ( g p ) +e ( p , 1 v i ) ( f s / 2 +1 ) ( n 一 p ) / 2 +( ( b / 2 1 +1 ) ( 二 一 p ) 因此p n 一2 r r a / 3 ( 6 / 2 ) +1 ) ， 进而% ( g ) =2 p 一 ， 2， 一4 m / 3 ( b / 2 1 +1 ) .证 毕. 当d =3 时， 定理 3 . 1 7 中所给出的界是可达的. 当n_5 时， 定义1 * 如下: v ( y ) 二 。 ， 。 w , s , t , e ( 1 ) =( u w , u s , u t , v s , v t , v to , w s , w t i 图 1 . 按下 述 情形 来 构 造图 : 若、 二 5 k , 作k 个1 的 拷贝g i , g 1 . . . . . . . . g k , v ( g i ) = n i , v i , w i , s i , t i , e ( g i ) = a i w i , n i s i ， 二 : t i ， 二 : s i , v i t i , v i w i , iu i s z , w i t i i ， 其中 顶 点。 i , v i , w i , s i , t * 分别是i ”中顶点。 i v , w , s , t 在g : 中相对应顶点.当。=5 时， 将 顶 点。 和 顶点 相连即 可. 构 造图l i : 1 j =( 1 ( i i ) , e ( i i ) ) ,y ( 1 i ) =u 挺 ， 州g i ) , e ( y , ) =u 挺 t e ( g i ) u 牡 尹 : : 、， :+ 土 u v k fl l ， 易 知 ，l l ( ) i ) l =5 k , je ( y i ) l =9 k . 由 定 理， 可得7 3 ( 1 1 ) ? 5 k 一 4 / 9 ( 9 k ) =k ， 当i =1 , 2 , ， k 时， 令f ( s s ) =一 i ,f ( t i ) =一 1 , f ( u i ) = f ( v i ) = f ( w i ) =1 ， 可 验 证j 为) -i 一个符号控制函 数， 且uu ( f ) = k ， 从而 y . ( y i ) s k ， 故- y . 0 1 ) =k . 若n 二5 k +1 时， 构造图1 2 : 1 2 =( 川i 勺， e ( i 的 ) ， y ( 1 2 ) 二v ( 1 ; u a , e ( 1 2 ) =e(ii) u a u , . 若， =5 k + 2 时， 构造图1 3 : 1 3=( v ( 1 a ) , e ( l a ) ) , i ( 1 a ) =v ( 1 2 u扣 ， e ( 1 3 ) 二( e ( 1 2 ) 一。 * 、 ， ) u g v k .若 ? : =5 k +3时， 构造图 、 4 : ) 4=( 1 - ( 1 a ) , e 。 一; ) ) , i ( 1 一， ) =1 ( ) 3 u c , e ( 1 a ) = e ( 1 8 ) u c u i . 若? l =5 k + 4 时， 构造图1 5 : 1 5 =( i ( ) s ) , e ( l a ) ) , v ( i 5 ) =1 ( ) 4 u d , e ( y 5 ) =( e ( 1 4 ) 一二 ; w 1 ) u t h a t . 同 样可验证对于图1 ( i =2 , 3 , 4 , 5 ) , 有7 s ( 1 = ) = n 0 篮 ) 一4 7 n ( ) i ) / 9 1 ( : =2 , 3 , 4 , 5 ) . 定理3 . 1 8对于任意图g , n = i v ( g ) i , b = a ( g ) , .-a =, ( g ) ， 有 7 3 ( g ) 怀 * +2 一 ) n / ( b +2 + ) . 证: 由引 理 3 . 1 5 我们可知，。 ( 只m) ( 6 1 2 1 +1 ) ( 二 一 p ) ， 因 而p中 存在一个顶点 x ， 使 得! 至 少 与m中( ( s / 2 1 + 1 ) ( n 一 p ) / p 个 顶 点 相 邻 . 因 为l . u c n x f ( u ) - 1 , 硕士学位论文 ma s t e r， s i t 比 sts 从而x至少与p中( f 6 / 2 1 +1 ) ( n 一p ) l p 个顶点相邻.因此 d g ( 二 ) 2 ( d / 2 +1 ) ( ， 卜 p ) l p 由上式我们可得到p 全( 夕十2 ) n / ( 8 + 2 +么 ) ， 因 而 7 , ( g ) =2 p 一。 ( b +2 一a ) r a / ( b +2 + ) . 证毕 定理 3 . 1 9对于任意图g， ( t en , r 1 ) ， 则有 。 = v ( g ) j , r =p ( g ) , a=a( g ) ， 若 一 2 r ) n / ( s 十 2 + 2 r ) 证: 因a2 r +1 ， 故p中任意一个顶点至多 与:1 ! 中: 个 顶点相邻， 因 而。 ( p , a i ) r p ， 根据引理 3 . 1 5 ， 我们有 ( b / 2 +1 ) ( r 一 p ) 1 ) ， 则 有 二 1 - ( g ) 1 . 6 - =6 . ( g ) , ,=, ( g ) ， 若 =2 1 7 3 ( g ) ( 6 +2 一 ) n / ( 6 +2 + ) 推论3 . 2 1对于任意图g , n 二】 v ( g ) i , 6 =6 ( g ) , -a=0 ( g ) ， 若=2 r +1 ( : e n , : 1 ) , 则有 -y s ( g ) 协 * +3 一 ) n / ( 6 +1 + ) . 硕士学位论文 m ta s t e r s t h e s i s 互 3 . 3 关于界的比较 先将定理 3 . 1 0 一 定理 3 . 1 2 和定理 3 . 1 6定理 3 . 1 9 的下界列表如下: 定 理3 . 1 0 的 下 界 记 为l b , = 2 ( f下丽 一 1 ) / 2 一 。 ， 定 理3 . 1 1 的 下 界 记 为l b b 二 n 一2 m / 3 ， 定理 3 . 1 2 的下界记为l b , =( 6 ( g ) + 2 一 ( g ) ) n / ( 6 ( g ) + 2 + 0 ( g ) ) , 定 理3 .1 6 的 下 界 记 为 : 。 ， 一 2 ( 了 。 ， + 8 (6 - + 2 ) n ) / 4 卜n ， 定 理3 .1 7 的 下 界 记 为 l b : 二n 一 4 m / 3 ( 6 * / 2 1 +1 ) ， 定 理 3 . 1 8 的下界记为 l b 3 二( 6 * + 2 一a ) 7 a / ( 6 * + 2 + a ) ， 定 理 3 . 1 9 的下 界记为 l b ; 二( p+3 一 ) n / ( 6 * +1 + ) . 先 比 较l b a 和l b , 的 大 小 考 察 函 数i (二 ) 二 2 ( ( 了 x 2 + 8 (3 + 2 )n 一 x ) / 4 ) 一 ，; ， (2 0 ，j (二 ) 为 递 增 函数. 因为6 * 2 ， 当6 * 3 时， 我们有f ( p ) f ( 2 ) ， 从而l b , , 2 ， 从而 l b , 一l b , =2 n i ( ( ( 6 1 2 1 一1 ) ) / 3 ( 千 6 1 2 1 +1 ) 。 ， 当6 * 3时，l b l b , ， 因而定理 3 . 1 7 的下界优于定理 3 . 1 1 的下界. 最后，比 较l b , , l b , 和l b 。 的大小 考察函数 9 ( x ) 二( x 十 2 一 ) / ( x 十 2 + -a ) , ( 0 x 6 ， 我们有l b w 1 对v e 1 1 ( g ) ， 因l u c n v s ( - ) 1 ， 即 in v n p 一n ( v n a l l 1 ， 又!n v i =i n v n p i +i n v n fl i i =d ( v ) +1 , 从而n , - n p i d ( v ) / 2 +1 ， 即n川n p i d ( v ) / 2 +1 . 又 e ( 1 一 ， 、 + ) =又 ., u 1 n ， + 卜 艺 n r n p j 又 ( ( d ( v ) l 2 ) + 1 ) u x 一1 1 任万 一u 任入 一 证毕. 引理4 . 3对。阶二分图g = 汀， y , 习， 采用引 理 ， e f l e r n 4 . 2 的记号，若.a - 7 $ ， 则 e ( x 一 ， 、 十 ) ( b / 2 ! 十1 ) 一 一 . 证:由符号控制数的定义和引理可知，若xe iv ， 则，e s ( g ) . 当二ex一时，有 d ( 劝 b . ， 代入引理4 . 1 中 即得.证毕. 定理4 . 4若g二( x , 艺e ) 为、阶二分图，b = b ( g ) ， 则 % ( ) 2 j 4 ( b + 2 ) n +( b + 2 ) 2 一 ( b . + 2 ) 1 / 2 1 一 n 证; 采用引理 r e fl e m 4 . 2 的 记号， 记 x1 1 = k , 1 1 + 1 情形 1 : 若s ( g ) = 4 ? ， 由引理 3 . 1 3 知，7 9 ( g ) 情形 2 : 若s ( g ) 4 ， 则x一与y 一中至少有一个非空，不妨设x- 0 4 . 情形2 . 1 若3 ,- - :a (h ， 从而k 十l 2 ， 据引 理4 .2 e ( x - , y + ) ( f a / 2 +1 ) i x 一 . y +中至少存在一点 2 ， 使得 二至少与 x+中 f f ( f b / 2 1 + 1 ) ix- 11 / 1 1个点相 硕士学位论文 m a s t e r s i f i r s t s (l)(z) 邻， 故k ( b / 2 1 +1 ) i x 一 1 / l ， 即 k l ( 6 1 2 1 +1 ) jx一 k l ( 6 / 2 1 +1 ) i 1 一 由( 1 ) , ( 2 ) 式可得 2 k l ( 6 / 2 1 +1 ) o a 一 +11 一 ) =( 6 . / 2 1 +1 ) 。 一( k + l ) 又由 ( k + l ) 2 = k 2 + 1 2 + 2 k l 4 k l 2 ( 6 * / 2 1 +1 ) 7 一( k + l ) 1 令 k +l 二v ， 可得 v z +( +2 ) 1/ 一( d * +2 ) l 1 。( 3 ) 由v 0 。 解方程(