（系统理论专业论文）正则图的upper减控制数.pdf

正则图的u p p e r 减控制数 摘要 帅1 1 1 l l 1 1 1 1 1 洲1 1 1 l l | | 1 1 1 1 1 l l l l y 18 0 4 5 0 4 图g = ( me ) 上的函数，：v 一 一1 ，0 ，1 】被称为是图g 上的一个减控制 函数，如果对任意的点t ，v ，都有，( m ) = ，( u ) 1 减控制函数，是图 g 上的极小减控制函数，如果不存在减控制函数夕：v _ 一l ，o ，1 ) ，夕，使 得对任意的点 kg ( v ) ( v ) 都成立图g 的减控制数通常表示为，y 一( g ) ， 它为g 上所有的减控制函数之中权重的最小数值；图g 的u p p e r 减控制数记为 f 一( g ) ，它是图g 上所有的极小减控制函数之中权重的最大数值也即是： ，y 一( g ) = m i n u ( ) i ，为g 上的减控制函数) 和 r _ ( g ) = m a x w ( f ) i ，为g 上的极小减控制函数) 图g = ( ke ) 上的函数，：e 一 一1 ，o ，1 ) 被称为是图g 上的减边控制 函数，如果对于图g 的每一条边e e 都有，( 【e 1 ) = ( e ) 1 图g 的 e e n i h 减边控制数通常表示为( g ) ，它为图g 上所有的减边控制函数之中权重的最 小数值；图g 的u p p e r 减边控制数记为r ，m ( g ) ，它是图g 上所有的极小减边控制 函数之中权重的最大数值也即是： 7 一( g ) = m 饥扣( ，) i ，为g 上的减边控制函数) 和 r - ( g ) = m a x w ( f ) i ，为g 上的极小减边控制函数) 本文通过对图的结构性质的分析，得到了正则图的u p p e r 减控制数。主要结 论如下： ( 1 ) 对任意的礼阶三正则图g 都有r _ ( g ) 兰n ，且此界是可达的，并构造 o i 出一类r 弋g ) = 三n 的图； 对任意的礼阶四正则图g 都有r - ( g ) 南n ； 对任意的竹阶五正则图g 都有r _ ( g ) 三佗； ( 2 ) 对任意的礼阶七一正则图g 都有r 一( g ) 妄 高n ； ( 3 ) 对于任意的有m 条边的三正则图g 都有r 二( g ) 了2 m 关键词：三正则；四正则；五正则；k 一正则；减控制数；减边控制数 一 u p p e rm i n u s d o m i n a t i o nn u m b e ro fr e g u l a r g r a p h s a b s t r a c t l e tg = ( ke ) b eag r a p h ，af u n c t i o nf ：v _ - 1 ，0 ，1 ) d e f i n e do nt h e t h ev e r t i c e so fgi sam i n u sd o m i n a t i n gf u n c t i o n ，i ft h es u mo fi t sf u n c t i o nv a l u e so v e r a n yc l o s e dn e i g h b o r h o o di sa tl e a s to n e t h a ti s ，f o re v e r yv e r t e xt ，v ，( m ) = f ( u ) 1 am i n u sd o m i n a t i n gf u n c t i o nfi sm i n i m a l ，i ft h e r ed o e sn o te x i s t a n ym i n u sd o m i n a t i n gf u n c t i o ng ：v _ ( 一1 ，0 ，1 ) ，f g ，f o rw h i c hg ( v ) f 0 , ) f o re v e r yv e r e xt ，v t h em i n u sd o m i n a t i o nn u m b e ro fa g r a p hg ，d e n o t e d ，y 一( g ) i st h em i n i m u mw e i g h to fa l lt h em i n u s d o m i n a t i n gf u n c t i o n so fg ：t h eu p p e rm i n u s d o m i n a t i o nn u m b e ro fag r a p hg ，d e n o t e df _ ( g ) ，e q u a l st h em a x i m u m w e i g h to fa l l t h em i n i m a lm i n u sd o m i n a t i n gf u n c t i o n so fg t h a ti s ，y _ ( g ) = m i n w ( f ) ifi s 口m i n u sd o m i n a t i n gf u n c t i o no ng ) a n d r 弋g ) = m a x w ( f ) jfi s 口m i n i m a lm i n u sd o m i n a t i n gf u n c t i o no ng l e tg = ( k e ) b eag r a p h ，af u t i c t i o nf ：e _ - 1 ，0 ，1 ) d e f i n e do nt h e t h ee d g e so fgi sam i n u se d g ed o m i n a t i o nf u n c t i o n ，i ft i i es u mo fi t sf u n c t i o nv a l u e s o v e ra n yc l o s e dn e i g h b o r h o o di sa tl e a s to n e t h a ti s ，( 【e 】) = f ( e 7 ) 1f o r e v e r ye e t h em i n u se d g ed o m i n a t i o nn u m b e ro fa g r a p hg ，d e n o t e dt ( g ) i s t h em i n i m a lw e i g h to fa l lt h em i n u se d g ed o m i n a t i n gf u n c t i o n so f g ；t h eu p p e rm i n u s e d g ed o m i n a t i o nn u m b e ro fag r a p hg ，d e n o t e dr 幺( g ) ，i st h em a x i m u mw e i g h to fa l l t h em i n i m a lm i n u s e d g ed o m i n a t i o nf u n c t i o n so fg t h a ti s t ( g ) = m i n w ( f ) i f i snm i n u se d g ed o m i n a t i o nf u n c t i o no ng ，a n d i i i r 幺( g ) = m a x ( w ( f )if i sam i n i m a lm i n u se d g ed o m i n a t i o nf u n c t i o no ng ) b yc o n s i d e r i n gt h es t r u c t u r a lp r o p e r t i e so fg r a p h s ，t h i st h e s i ss t u d i e st h eu p p e r m i n u sd o m i n a t i o nn u m b e ro fr e g u l a rg r a p h s t h em a i nr e s u l t so b t a i n e di n t h i sd i s s e r t a t i o n m a y b es u m m a r i z e da sf o l l o w s ： ( 1 ) i fg i sat h r e er e g u l a rg r a p ho f o r d e rn ，t h e nr 一( g ) a n dt h e r ee 础ac l a s s 。f 酉a p h s ，f o rw h i c hf 一( g ) = 暑n ； ( 2 ) ( 3 ) 善佗，m e r e s u l t i ss h 唧 i fgi saf o u rr e g u l a rg r a p ho fo r d e rn ，t h e nf 一( g ) i fgi saf i v er e g u l a rg r a p ho fo r d e rn ，t h e nr 一( g ) 7 而礼； 3 互佗； i f g i sa 七一r e g u l 哪a p h 。f o r d e rn , t h e n f - ( g ) 赫 i f gi sat 1 1 r e er e g u l a rg r a p h 。f s i z em ，t h e nr k ( c ) 了2 m 佗： k e yw o r d s ：t h r e e r e g u l a rg r a p h s ；f o u rr e g u l a rg r a p h s ；f i v er e g u l a rg r a p h s ； k r e g u l a rg r a p h s ；u p p e rm i n u sd o m i n a t i o nn u m b e r ；u p p e rm i n u se d g ed o m i n a t i o n n u m b e r i v 目录 摘要i a b s t r a c t m 目录v i 1 绪论1 1 1 基本概念 1 i 1 1 关于图的点控制的研究背景和一些概念：o 2 2 1 1 2 图的点控制数的研究背景2 1 1 3 关于图的边控制的一些概念4 1 2 研究概况 6 1 2 1 图的点控制数的研究概况：6 1 2 2 图的边控制数的研究概况8 l - 3 本文的主要结果9 2 三、四、五正则图的u p p e r 减控制数1 0 2 1 引理1 0 2 2 主要结果1 0 3 七二正则图的u p p e r 减控制数2 5 4 三正则图的减边控制数3 1 4 1 引理3 l 4 2 主要结果3 2 参考文献3 7 在学期间的研究成果及发表的论文4 0 致谢4 l 浙江师范大学学位论文独创性声明4 2 学位论文使用授权声明4 2 v 浙江师范大学学位论文诚信承诺书4 3 v i 1 绪论 1 1 基本概念 在本文中，我们定义一些本学位论文中要用到的图论的基本术语与符号 设v ( g ) 是有礼个元素m 1 ) 的集合，e ( g ) 是v ( g ) 的某些二元子集所 形成的集合，称有序对g = ( y ( g ) ，e ( g ) ) 为一个有限简单无向图，简称为图 把v ( g ) 称做图g 的顶点集合v ( g ) 中的元素称做图g 的顶点，g 中顶点的个 数i y ( g ) i 称做图g 的阶，把e ( g ) 称做图g 的边集合，e ( g ) 中的元素称做图 g 的边常用y ，e 分别表示图g 的顶点集合与边集合如不特殊说明一般记 g = ( y ( g ) ，e c g ) ) 为g = ( ke ) 没有重边和环的图叫做简单图除非特别指 出，本文研究的图均指有限简单无向图 常用让，t ，表示图g 中的点，用e 表示图g 中的边若边e = u t ，6e 。则说点 t ，u 在图g 中相邻；这时又说点u 和t ，是e 的两个端点，也说点t ，u 与e 是相关 联的设u 是图g 的一个顶点，图g 中与点t ，相邻的点所形成的集合叫做t ，( 在 图g 中) 的开邻域，记作g ( u ) 简记作( t ，) ( t ，) u 口) 叫做t ，( 在图g 中) 的闭 邻域，简记作m 在图g 中与u 相关联的边的条数叫做u 的度数，记作d g ( u ) ， 简记作d 0 ) 图g 中的点的最小和最大的度数分别记作6 ( g ) 和( g ) 若对任意 的钞6k d ( 口) = k ，则称图g 是k 一正则图；若对任意的t ，6kd ( ) = k 一1 或者 k ，则称图g 是拟七一正则图 设g = ( ve ) 是一个图，若集合u ( u 冬y ) 中的任意两个顶点都不相 邻，称u 为图g 的一个独立集若图g 的顶点集合y 可剖分成r 个独立集： ，k ( u u uk = v ) 且k nk = ，i j ，i = 1 ，2 ，r 则 称g 为r 部图特别地当r = 2 时，g 为二部图 1 1 绪论 1 1 1 关于图的点控制的研究背景和一些概念 1 1 2 图的点控制数的研究背景 图的控制理论的研究来自于一个趣味数学游戏：在一个8 8 的棋盘上，需要 放置多少王后才能攻击所有的方格? 最后，人们得到至少需要5 个王后才能攻击 所有的方格 棋盘方格的控制问题放到图里面就转化为一般的图中点的控制问题 1 9 6 2 年，b e r g e 和o r e 最早引进了控制集的概念；1 9 7 7 年，在c o c k a y n e h e d e t n i e m i 的一篇文献综述中最早使用了图的控制数的符号，y ( g ) ，并给出了关于图的控 制数的一些结果：1 9 9 8 年，h a y n e s h e d e t n i e m i s l a t e r 的专著讨论了控制集及其变 形 1 】减控制就是点控制推广之中的一类，减控制背景是很丰富的：现实中由个 人或者团体构成的网络图，每个人代表图表中的一个点，要求对某一事件做表决， 每个人都有一个初始的意见一票，假设+ l 点表示此人持支持态度，0 点表示持 中立态度，一l 点持反对态度，但是最终意见是受个人和与此人相邻的人的票数决 定的，即在个人和此人的邻人构成的团体中支持的票数多于反对的票数，我们才 称此人为赞成决定，此人代表的点为图表中的赞成点，否则称此人代表的点为图 表中的反对点我们寻求一个指派，使得全体中每个人的最终意见都是赞成决定 的在这些指派中我们最感兴趣的是那些能令每个人最终意见都是赞成的持支 持态度的人的最少个数( 统一指派) ，而极小减控制数就是这些统一指派中所有的 + l ( 支持) ，0 ( 中立) ，1 ( 反对) 的数值和的最小值u p p e r 减控制数就是所有统一指 派中的和的最大值【2 】 给定图g = ( ve ) 的顶点集合y 的一个子集s ，集合s 中的所有点的邻点 所形成的集合称做集合s ( 在图g 中) 的开邻域，记作( s ) n ( s ) u s 叫做集合s ( 在图g 中) 的闭邻域，记作吲d s ) 表示与点t ，相邻的点在集合s 中的个数 集合以w 是图g 的顶点集合y 的两个不交的子集，在点控制中常用e ( 阢) 表示子集u 和子集之间边的条数项点集合y 的一个子集s 称为控制集，若 2 1 绪论 图g 中的任何一个顶点u v s ，都存在点心s 使得u ，u ( 在图g 中) 相邻 给定一个图g ，可能会有许多个不同的控制集，在所有的控制集中包含顶点个数 最少的控制集称为图g 的一个最小控制集，一个最小控制集所包含的顶点数目 即为图g 的控制数 定义1 1 【3 】对于图g = ( e ) 上的一个实值函数f ：v r ，的权 重为w ( f ) = e ，( u ) ，对于s v ，我们定义f ( s ) = e ，( u ) ，这样就有 ”y ( g ) y e s w ( f ) = ，( y ) 函数，在图g 上是极小的，如果不存在函数9 ：v _ r ，f 夕，使 得对任意的 kg ( v ) f ( v ) 成立 定义1 2 【4 】设g = ( ke ) 为一个图，一个双值函数f ：v 一 o ，1 ) 如果对任 意的点心v ，均有f l y l = ，( u ) 1 成立，则称，为图g 的一个控制函数， 图g 的控制数定义为 ，y ( g ) = m i n w ( f ) l ，为图g 的一个控制函数】 定义1 3 设g = ( ve ) 为一个图，一个双值函数f ：v _ 一1 ，1 ) 如果对任意 的t ，v ，均有，m = ，( u ) 1 成立。则称，为图g 的一个符号控制函 数( s i g n e dd o m i n a t i o n ) 。图g 的符号控制数定义为 ( g ) = m i n 0 4 f ) i ，为图g 的一个符号控制函数) z e l i n k a 5 】把图的符号控制中的点的闭邻域的函数值换成点的开邻域的函数 值得到了全符号控制的概念，即： 定义1 4 设g = ( ke ) 为一个图，一个双值函数f ：v _ 一1 ，1 ) 如果对 任意的秒v ，均有f v 】= f ( u ) 21 成立，则称，为图g 的一个全符号控 u ( ，) 制函数( s i g n e dt o t a ld o m i n a t i o n ) ，函数，在图g 上是极小的，如果不存在函数 g ：v _ - 1 ，1 ) ，f g ，使得对任意的t ，k 夕( u ) f ( v ) 成立图g 的全符号 控制数和图g 的u p p e r 全符号控制数定义为 7 0 t ( g ) = m i n o j ( f ) if 为图g 的一个全符号控制函数) ， n c ( g ) = m a x w ( f ) i ，为图g 的极小全符号控制函数) 3 1 绪论 有时全符号控制数和u p p e r 全符号控制数也记为w ( g ) 和r s ( g ) 【6 】 定义1 5 【3 】设g = ( ve ) 为一个图，一个三值函数，：v _ ( - 1 ，0 ，1 如果 对任意的点 v ，均有i v 】= f ( u ) 1 成立，则称，为图g 的一个全符 u j ( t ，) 号减控制函数( m i n u st o t a ld o m i n a t i o n ) ，函数，在图g 上是极小的，如果不存在 函数夕：v _ 一1 ，0 ，1 】，夕，使得对任意的t ，vg ( v ) f ( v ) 成立图g 的全符号减控制数和图g 的u p p e r 全符号减控制数定义为 7 一( g ) = m i n w ( f ) f 为图g 的一个全符号减控制函数) ， r _ ( g ) = m a x w ( f ) i ，为图g 的极小全符号减控制函数】 定义1 6 设g = ( ve ) 为一个图，一个三值函数f ：v 一 一1 ，0 ，1 ) ，如果满足 条件：对y 的每个顶点 ，均有f l y 】= f ( u ) 1 成立，则称，为图g 的一个 减控制( m i n u sd o m i n a t i o n ) 函数一个减控制函数是极小的，如果不存在减控制 函数夕：v 一【一1 ，0 ，1 ) ，f g ，使得对任意的u kg ( v ) f ( v ) 成立g 的减 控制数和u p p e r 减控制数分别记为： ，y _ ( g ) = m i n w ( f ) i ，为g 上的减控制函数) ， r 一( g ) = m a x w ( f ) i ，为g 上的极小减控制函数) 1 1 3 关于图的边控制的一些概念 图g = ( ke ) 中边的条数为m = i e l 对于一条边e e ，边e 的开邻边为 n ( e ) = u u = e eiu e 或者u e ) ，边e 的闭邻边为g e 】= g ( e ) u e ) 对于子集s e ，经常用d s ( e ) 表示集合s 中与边e 相邻的边的条数在图的边 控制中，对于两个不含相同边的集合和，常用e ( 以) 表示集合u 中的边与 集合相关联的边的条数，它也等于集合中的边与集合u 相关联的边的条 数，因而也等于集合u 与公共点的个数对于图g = ( ke ) 上的一个实值函 数，：e r ，对于子集s e ，通常记f ( s ) = ，( e ) e 6 s 定义1 7 【4 】设g = ( ke ) 是一个非空图，d e ，如果对于任何一条边 e e d ，均存在边e d ，使得边e 和e 在图g 中相邻( 即有一个公共点) ，则 4 1 绪论 称集合d 为图g 的一个边控制集图g 的边控制数定义为 y ( g ) = m i n l d i ：d 为图g 的边控制集) 对于空图瓦，则定义r ( 琢= o ) 符号边控制问题的提出【4 】：如果将一个给定的图g = ( me ) 的边集划分 成两类( 即e = e 1u 易) ，使得第一类边是局部占优的( 即g 的每条边的闭邻域 中第一类边多于第二类边) ，问这两类边的数目之差i e l l l 岛i 至少为多少? 基于上述问题，提出如下符号边控制数概念： 定义1 8 设g = ( ke ) 是一个非空图，一个函数f ：e _ 一1 ，1 ) 如果满足 f ( e 7 ) 1 对于每一条边e e ( g ) 均成立，则称，为图g 上的一个符号边 e e n l 4 控制函数图g 的符号边控制数定义为 z ( g ) = r a i n ，( e ) l ，为g 的一个符号边控制函数 ， c 阜( g ) 并且对于空图g = 瓦，则定义亿( 一= o ) 定义1 9 【7 】设g = ( ke ) 是一个非空图，一个函数，：e _ 一1 ，o ，1 ) 称为 图g 上的一个减边控制函数，如果对于图g 中每一条边e 均有，( e ，) 1 e l v 4 成立图g 的减边控制数定义为 以( g ) = r a i n ，( e ) i ，为g 的减边控制函数) ， , e e ( g ) 类似于图的点控制函数中极小函数的定义，图g 的u p p e r 减边控制数定义为 r ，m ( g ) = m a x w ( f ) i ，为g 上的极小减边控制函数 并且对于任意空图g = 霹，则定义嘛( 面= o ) 5 1 绪论 定义1 1 0 4 】设g = ( ue ) 是一个n 阶连通图3 ) ，一个函数，：e _ 一1 ，1 ) 称为图g 的一个符号边全控制函数，如果对于g 中每一条边e 均有 ，) 1 成立图g 的符号边全控制数定义为 e e n ( e ) 。( g ) = r a i n ，( e ) i ，为g 的符号边全控制函数) ， e e e ( g ) 并且定义。( k 1 ) = 0 和t 。( ) = 0 本文未提及的术语和符号请参见文献【8 】或者文献【4 】 1 2 研究概况 1 2 1 图的点控制数的研究概况 图的控制集及其变形至今已有很深入的研究 口1 9 9 6 年，b z e l i n k a 9 】得到图的符号控制数的一些结果： 如果g 是凡阶三正则图，那么仉( g ) i - t n ，且此界是可达的 如果g 是n 阶- - i f _ 2 , u 图，那么，y 一( g ) 妄n 口1 9 9 9 年，z ez h a n g 等人 1 0 】得到关于符号控制数的下界的一些结果： 对于任意的n 阶图g ，都有( g ) 2 - 1 + v 佰+ 8 h i 一几，且此界是可 达的 若图g 的阶数为n = i v ( a ) l ，边的条数为仇= i e ( g ) i ，则( g ) n 一丢m 对于任意的佗阶图g ，都有( g ) 簧吕黼n 口2 0 0 1 年，b z e l i n k a 和l i b e r e c 【5 】得到图的全符号控制数的结果为 令g 为一个，正则图，如果r 是奇数，则n r ；如果7 是偶数，则 t 2 n r 口2 0 0 4 年，m a h e n n i n g 6 1 又得到了关于拟k 一正则图的全符号控制的结果： 6 1 绪论 职哪k 2 + i 襄淼 且此界是可达的 口2 0 0 7 年，h y a n 3 】等人得到三、四正则图的全符号减控制数的结果： 若g 是佗阶- - i e 贝u ，则耳( g ) 兰礼，此上界是可达的并构造出了可以 达到此上界的一类图 若g 是n 阶四正则图，则r r ( a ) 而1 佗，此上界是可达的并构造出了可以 达到此上界的一类图 口1 9 9 6 年，j d u n b a r , s h e d e t n i e m i ，m a h e n n i n g ，a m c r a e 【11 】得到关于图的 减控制算法的结果： 图的减控制集是n p 完备的，即使是限定在二部图上 图的u p p e r 减控制集是n p - 完备的，即使是限定在二部图上 图的u p p e r 减控制集是n p - 完备的，即使是限定在弦图上 口1 9 9 8 年，l yk a n g 和m c c a i 【1 2 】得到下面的结果： 如果g 是n 阶三正则图，那么r 弋g ) 丢n 口1 9 9 9 年，j d u n b a r 等人【2 】等人得到图的减控制数的结果为： 对任意的图g ，都有，y 一( g ) ，y ( g ) 他们在此文献中给出了如下猜想： 若g 是仃阶二部图，则7 - ( g ) 4 ( v r n - 干1 。一1 ) 一n 上面的猜想已被证明【4 】 口2 0 0 4 年，l yk a n g 等人 1 3 】把此猜想的结果改进为 令k 2 ，对于任意的n 阶蠡部图g = ( ke ) ，都有 ，y 弋g ) 之告( v 1 + 2 ( k k1 ) n _ 1 ) 一 1 绪论 口2 0 0 0 年，l y k a n g 和m c c a i 【1 4 】又得到了关于图的减控制数的结果： 若g 是礼阶7 一正则图，则 州哪、r + l 孓，篡 口2 0 0 1 年，c x w a n g 和j z m a o 【1 5 】给出了关拟正则图的减控制数的上界的结 果： 若g 是佗阶拟k 正则图，则 且此界是可达的 吖哪 鬃二： 1 2 2 图的边控制数的研究概况 角为偶数 k 为奇数 对于边控制数的研究至今也很深入 口1 9 9 9 年，b z e l i n k a 和l i b e r e c 【1 6 】得到关于超立方体图的边控制数的结果： 若q n 是超立方体图，则对任意的正整数n ，都有q ( q n ) 2 驴1 若q 。是超立方体图，则对任意的正整数死，都有t ( q n ) 2 俨1 口2 0 0 3 年，徐保根 1 7 】得到关于图的符号边控制数的结果： 对于任意的n 阶图g ，若i e ( g ) i = m 1 ，则 们) f 竺坠裟掣1 口2 0 0 8 年，s j a h a n b e k a m 1 8 1 5 l 有- 下面的结果： 若g 是n 阶图，则t ( g ) 【芸n l j 8 1 绪论 口2 0 0 6 年，b x u 【1 9 】得到符号边控制的结果为： 对任意的n 4 ) 阶图g ，都有 们) 这里 b = q l o + p a o p o l 一3 m 3 0 综合( 2 7 ) 和( 2 8 ) 式可以得到： r 一( g ) = p 一仇 ( 2 8 ) 55 1 百几一面n + 石6 = 丢n 一去【5 ( g 。+ 9 2 0 - j r p 1 0 + 2 p z 。+ 。+ 3 m 3 。) 一4 ( g - 。+ 仇。一加 - 3 m a o ) 】 = 詈n 一去( 口- 。+ 5 他。+ 5 p - 。+ 1 0 p z 。+ 6 p 3 。+ 2 7 m 3 。+ 4 册- ) 争 下面构造一类图证明界鲁n 是可达的： 令g = ( ke ) 为一个图，图g 中顶点的集合为v = u 叁l a ，其中a 1 = 1 2 , j lj = 1 ，2 ，七) ；a 2 = o 巧ij = 1 ，2 ，尼) ；a a = 1 2 3 j lj = 1 ，2 ，3 七) ； a 4 = 1 2 , j i 歹= l ，2 ，3 七) ；则i a l i = i a 2 i = k ，i a s i = i a 4 i = 3 k ，k = 1 ，2 ，3 ， 则图g 的阶数n = l a l i + i a 2 i + i a a i + i a 4 i = 8 k 图g 中边集e 的构造如下： 1 把每个o u 与n 33 j ，1 2 3 巧一1 ，0 , 33 j 一2 ，j = 1 ，2 ，k 相连，n 巧也与1 2 3 巧，1 2 3 巧一1 ， 1 2 3 巧一2 ，j = 1 ，2 ，k 相连； 1 4 ；弓m 3 一 册 一 o黜 + m 沁 抚 1 6 1 6 一 一 p p 1 6 1 6 1 6 一 p，1手16 ，l l 一 p p 5 6 一 一一 2 三、四、五正则图的u p p e r 减控制数 2 把n 巧与a 4 j ，j = 1 ，2 ，3 七相连； 3 把口幻与a 4 j + l ，j = 1 ，2 ，3 k 相连( a 43 k + 1 = 口41 ) ，则我们得出的图g 是 三正则的 构造图g 上的一个减控制函数，如下： l l i ，( u ) = 0 l1 t ，a 1 ， t ，a 2 a sua 4 则显然对图g 中每个点t ，都有，m 1 ，因而，是图g 上的减控制函数又 对任意的顶点v a 2ua su 山，都有f ( v ) 0 ，且存在点t i n v 】i 1a s ， 使得，m = 1 ，由引理2 1 可知，是图g 上的极小减控制函数又f ( v ) = i a 3 i + i a 4 i i a l l = 5 k = 5 n 8 因而r 一( g ) 5 n 8 ，又由上面的证明可知 r 一( g ) 吾n ，所以r _ ( g ) = 吾佗，因而此界是可达的 当七= 1 和k = 3 时，图形如下： 门访 口l i 口2 i 口i i 口2 i a 1 2 口1 2 a 1 34 2 ， 七：1 k = 3 图l ：u p p e r 减控制数为5 n 8 的图 ( f i g u r e1 ：g r a p h so fu p p e rm i n u sd o m i n a t i o na r e5 r u 8 ) 定理2 2 若图g = ( ke ) 为四正则的，图g 的阶数n = l y i ，则r 一( g ) 孟凡 1 5 口棚 2 三、四、五正则图的u p p e r 减控制数 证明：设，为图g = ( e ) 上的一个极小减控制函数，则r 一( g ) = i p i i m i = p 一仇类似于定理2 1 ，只q 和m 进一步可细分为： 岛 q i j m i j _ 【u p id q ( v ) = i ，d m ( v ) = 歹，这里0 j 2 ，0 i 4 一巧) ， u q id p ( v ) = t ，d m ( v ) = 歹，这里0 j 2 ，j + 1 i 4 一j ) ， u m id r ( v ) = i ，d q ( v ) = 歹，这里0 j 2 ，【等j i 4 一歹) ) 令l 心l = p i j ，i q 玎i = ，i 坞l = 则 p = p o o + p l o + p 2 0 + p 3 0 + p 4 0 + p o l + p 0 2 + p n + p 2 1 ， q = q l o + q 2 0 + q 3 0 + q 4 0 + q 2 i + q 3 i ， m = m 2 2 + m 3 0 + m 3 1 + m 4 0 令p ：p 0 2up 2 1up 4 0 ；q 7 = q l ouq 2 1 ；m 7 = m 2 2um 3 0 很明显的，对任意的 顶点u p uq 7um ，都有f v l = 1 ，对任意的项点u v 一( p 7uq 7um ，) 都 有f l y 】2 由e ( q ，m ) 、e ( p m ) 和e ( p q ) 的定义，我们很容易得到下面的关系： e ( q ，m ) = q 2 i + q 3 1 = 2 m 2 2 + m 3 1 ； e ( p m ) e ( p q ) p o l + 2 p 0 2 + p l l + p 2 1 2 m 2 2 + 3 m 3 0 + 3 m 3 1 + 4 m 4 0 4 m 一( 2 m 2 2 + m 3 0 + m 3 1 ) ； p l o 十p l l + 2 p 2 0 + 锄l + 3 m o + 4 p 4 0 口1 0 + 2 q 2 0 + 2 q 2 1 + 3 q 3 0 + 3 ( 3 1 + 4 q 4 0 4 q 一( 3 q m + 2 q 2 0 + 2 q 2 1 + q 3 0 + q 3 1 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 由引理2 1 ，对任意的顶点t ，p p = up 1 0up 0 1up 2 0 ，都存在点 1 6 2 三、四、五正则图的u p p e r 减控制数 让m ，使得f u 】= 1 ，则点乱p uq 7um ，因而 p o o + p o t + p r o + p n + p 2 0 + p 3 0 冬e c p p ，p uq um ) = e ( p p ，只o ) + e c p p ，恳1 ) + e ( p p ，p 0 2 ) + e ( p p ，q ) + e c p p 7 ，m ) ( 2 1 2 ) 由引理2 1 ，对任意的顶点 ，必存在一个点t n v 】使得川叫= 1 ，因 而点u p ，u g ，如果点p ，那么点 不与p p ，的点相邻；如果点q ， 那么点 也不与p p ，中的点相邻，故e ( p 一一，4 0 ) = 0 由引理2 1 ，对任意的顶点 岛l 必存在一个点u n v 】使得，【u 】= 1 ，因 而点让p u um ，如果点t ，ep ，那么点u 至多与p p ，中的一个点相 邻：如果点q um 7 ，那么点t ，也至多与p p ，的一个点相邻因而我们可 把b 1 分成两个不交的集合： 爿1 = t ，p 2 1id p p ，( ) = 1 ) 和璐= p 2 1 一最l ， 令i 足l l = 玩l ，则i 磴i = 沈1 一区1 由于每个点t ，足l ，点 都至少要与集合 q 7um 的一个点相邻，故巧l e ( 最l ，um ，) - 因而 e ( p p ，岛1 ) = e ( p p ，爿l ，) + e ( p 一尸，磺) = 区1 + 0 e ( 爿1 ，u m ，) ( 2 1 3 ) 由引理2 1 ，对任意的顶点，必存在点u m 使得，心l = 1 ，因而 u p um 如果点口ep 7 ，那么点口至多与集合p p ，中的两个点相邻如果 点u m ，。那么点”也至多与集合尸一p 中的两个点相邻我们把岛2 分成两 个不交的点集： 昂2 = f id r , 一p ，( u ) = 2 ) 和f 器= f 如一瑞2 ， 1 7 2 三、四、五正则图的u p p e r 减控制数 令i 昂2 i = 2 ，则有i 磁i = p 0 2 一蕊2 由于任意的顶点钞昂2 ，点 至少要与m 7 中的一个点相邻，因而p 0 2 e ( 昂2 ，m ，) 从而有： e ( p p ，p 0 2 ) = = 2 1 + p 3 0 + p 4 0 2 p 0 2 + p 2 1 + p 4 0 + 2 m 2 2 + 3 m a o + q t o + 2 q 2 l 2 ，0 0 2 + p l l + p 2 1 + 伽l + 2 m 2 2 + 3 m a o + p l o + p i t + 2 p 2 0 + 2 p 2 1 + 3 p 3 0 + 4 p 4 0 一2 p 4 0 + q l o + 2 q 2 1 = 2 ( 2 t r 切+ 3 m 3 0 ) + 3 m 3 1 + 4 m 4 0 + 2 ( q l o + 2 q 2 1 ) + 2 q 2 0 + 3 q a o + 3 q 3 1 + 4 q 4 0 一2 p 4 0 = 4 m 一( y t t 3 1 2 m a o ) + 4 q 一( 2 q l o + 2 q 2 0 + q 3 0 + 9 3 1 ) 一2 p 4 0 = 4 ( q + m ) 一( 7 t t 3 1 2 m 3 0 + 2 q l o + 2 q 2 0 - t - q 3 0 + q 3 1 + 2 p 4 0 ) ( 2 1 6 ) 1 8 2 三、四、五正则图的u p p e r 减控制数 利用( 2 1 6 ) 式又可得到： 竹= p + q + m 5 ( q + m ) 一( 7 7 7 , 3 1 2 m 3 0 + 2 q t o + 2 q 2 0 + q s o + q 3 1 + 9 - p 4 0 ) 因而 ( 口+ m ) 亏1 n + 亏1 ( 讹l 一2 m + 2 口1 。+ 2 q 2 0 + q 3 0 + q 3 1 + 轨。) 由上式可得 p = n 一( q + m ) 吾( m 3 l 一2 m 3 。+ 2 9 l 。4 - 2 q 2 。+ 9 3 。+ 口3 1 + 2 矾。) = 1 g ( 2 1 7 ) 亏吼 这里a = m 3 1 2 m 3 0 + 2 q l o + 2 q 2 04 - q 3 0 + q 3 l4 - 2 p 4 0 利用式子( 2 9 ) 、( 2 1 0 ) 、( 2 1 1 ) 和( 2 1 5 ) 式可以得到： p = p o o + p o l + p 0 24 - p l o + p l l4 - p 2 04 - p 2 1 + p 3 04 - p 4 0 2 p 0 2 + p 2 14 - p 4 04 - 2 m 2 24 - 3 m 3 04 - q l o4 - 2 q 2 1 4 m 一( b 1 2 r a 3 0 ) + q l o + 4 m 2 2 + 2 m 3 1 2 q 3 14 - p 4 0 = 8 m 一( 7 t 3 1 2 m 3 0 ) 一( 2 7 7 2 3 1 + 4 m 3 04 - 4 m 4 04 - 2 q 3 1 一口l o p 4 0 ) = 8 m 一( 3 r a 3 t4 - 2 m 3 04 - 4 r a 4 0 + 2 9 3 l q l o p 4 0 ) 因而由上式可得 m 丢p + 丢( 3 + 2 m s o + 4 m + 2 q 3 1 - q l o - p 4 0 ) m 丢p + 弘1 这里b = 3 m 3 1 + 2 m 3 0 + 4 m 4 04 - 2 q 3 l q l o p 4 0 1 9 一 一 n n 4 5 4 5 一 一 2 三、四、五正则图的u p p e r 减控制数 利用( 2 1 7 ) 式和上式，则有： r _ ( g ) = p