（运筹学与控制论专业论文）图的几类符号控制.pdf

图的几类符号控制 摘要 图的控制参数理论是f _ l b e r g e 和o r e 共同建立的o r e 使用目前一直沿用的 控制数方面的术语7 d o m i n a t i n gs e t 7 和7 d o m i n a t i o nn u m b e r c o c k a y n e 和h e d e t n i e n i 概述了图的控制理论结果，并开始使用符号1 表示图g 的控制数控制参数方面的 研究逐渐成为一个公认的研究热点 h a y n e s 等人对控制理论作了系统的概述和说明图的控制理论方面的研究 已成为图论中发展最快的领域之一图的符号控制是图的控制理论的一个重要分 支，关于图的符号控制已经得到了很多有意义的结果，并利用图的符号控制关于 不同参数的界得到了几类特殊图的值 然而，对于一般图的符号控制的值仍然没有解决，因此图的符号控制的研究 是很有意义的 本人在前人研究工作的基础上继续研究，得到了以下几个结果： ( 1 ) 对于任意图g ，得到了两个符号控制数的界，并通过构造的方法证明了这 个界是可达的 ( 2 ) 对几类特殊图的符号全控制数进行讨论，得到了完全图，星图，扇图，轮图， 以及完全多部图的符号全控制数 ( 3 ) 提出t q 一符号控制数的概念，解决了图g 的g 一符号控制数关于不同参数的 下界，并通过构造的方法证明了其中一个下界是可达的 ( 4 ) 解决了后正则图的上限口一符号控制数的上界，并通过构造的方法证明了这 个界是可达的 关键词：符号控制函数，符号控制数，符号全控制函数，符号全控制数，q 一符号控 制函数，口符号控制数 i i s o m es i g n e dd o m i n a t i o nn u m b e r s o fg r a p h s a b s t r a c t d o m i n a t i n gp a r a m e t e ro ng r a p hw a s i n t r o d u c e db yo r ea n db e r g e c o c k a y n ea n dh e d e t n i e n ig a v eas u r v e yo nt h er e s u l t so fd o m i n a t i n gp a - r a m e t e ro ng r a p h s ，a n dd e n o t e db y7t h ed o m i n a t i o nn u m b e ro fag r a p hg t h ed o m i n a t i n gp a r a m e t e ro fg r a p h sh a se x t e n s i v e l yb e e ni n v e s t i g a t e di n t h ep a s t h a y n e se ta 1 s y s t e m i c a l l ys u m m a r i z e dt h ed o m i n a t i n gp a r a m e t e r t h e s t u d yo fd o m i n a t i n gp a r a m e t e r i ng r a p h sh a sb e e na ni m p o r t a n tb r a n c hi n g r a p ht h e o r ya n dc o m b i n a t o r i c s s o m ei n t e r e s t i n gr e s u l t so ns i g n e dd o m i n a t i o nn u m b e rf o raf e ws p e c i a lg r a p h sh a v eb e e no b t a i n e di nr e c e n ty e a r s h o w e v e r t h e r ea r em a n yo p e np r o b l e m so nt h es i g n e dd o m i n a t i o n n u m b e ro fg e n e r a lg r a p h s b a s e do ns o m ek n o w nr e s u l t s ，i nt h i st h e s i sw es t u d yt h ep r o b l e m so f s i g n e dd o m i n a t i o nn u m b e r s t h e m a i nr e s u l t so b t a i n e di nt h i st h e s i sa r e a s f o l l o w s ： ( 1 ) t w ot i g h tl o w e rb o u n d s o nt h ed o m i n a t i o nn u m b e ro fg e n e r a lg r a p h s a r ee s t a b l i s h e db yac o n s t r u c t i v em e t h o d ( 2 ) d e t e r m i n et h es i g n e dt o t a ld o m i n a t i o nn u m b e r sf o rs o m es p e c i a l g r a p h ss u c ha sc o m p l e t eg r a p h s ，s t a r s ，f a n s ，w h e e l s ，c o m p l e t em u l t i p a r t g r a p h s ，e t c ( 3 ) d e f i n eq - s i g n e dd o m i n a t i o nn u m b e r , o b t a i nq - s i g n e dd o m i n a t i o n n u m b e ro fag r a p hg w i t hr e s p e c tt od i f f e r e n tp a r a m e t e r s ，a n dp r o v et h a t o r eo ft h e s er e s u l t si ss h a r p i i i ( 4 ) g i v eat i g h tu p p e rb o u n do nu p p e rq - s i g n e dd o m i n a t i o nn u m b e ro f k - r e g u l a rg r a p h s k e yw o r d s ：s i g n e dd o m i n a t i o nf u n c t i o n ，s i g n e dd o m i n a t i o nn u m b e r , s i g n e dt o t a ld o m i n a t i o nf u n c t i o n ，s i g n e dt o t a ld o m i n a t i o nn u m b e r , q - s i g n e d d o m i n a t i o nf u n c t i o n ，q - s i g n e dd o m i n a t i o nn u m b e r i v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 黜魏氏研魄 学位论文使用授权声明 nv r 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生躲谚p 引导师躲 4 5 期。 一 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均己明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 4 7 承诺人( 研究生) ： 指导教师： 1 1 基本概念 1绪论 在本节中，我们引用了一些本学位论文中耍用到的图论的基本术语与符号 一个有序对g = ( v e ) 称为一个无向图，其中y 是一个有限集合，e 是y 中的不 同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图g 的 边通常用y ( g ) ，e ( g ) 分别表示图g 的顶点集合，边集合没有重边和环的图叫 做简单图本文研究的图均指有限简单无向图 用u ，v 表示图g 中的点，e 表示图g 中的边若边e = u u e ( g ) ，则说u ， v 在g 中相邻，或u 和v 互为邻点；这时又说u 和v 是e 的端点u 的全体邻点 所形成的集合叫做可的开邻域，记作( ) ，v 的闭邻域n ( v ) t 3 u ) ，记为m 设 集合acy ( g ) ，称n ( a ) ：= un ( v ) 为a 的开邻域，a 的闭邻域n ( a ) u a ) ， 记为【州若点u 是边e 的端点，则说v 与e 在图g 中相关联集合x 的势记 为l x l 图g 的补图记为召s 是v ( g ) 子集合，c s 1 是由s 导出的g 的子图如 果夕，是v ( g ) 映射到咒上的两个函数f 夕，对于 v 有g ( v ) ，( 可) ，则 记夕 f 一个函数厂是极小的当且仅当不存在函数夕f 使得夕 厂对于任 意v y ( g ) ，d e ( ) 表示v 在图g 中的度对于实数z ，记陋1 是不小于z 的最 小整数，记lzi 是不大于z 的最大整数v ( c ) 中互不相交的两个集合矿，记 e ( w ) 为连接u ，w 中顶点的所有边的集合 本节中未介绍的其他图论术语和符号基本上与文献【1 】中一致 定义在v ( g ) 的一个函数：f ：v ( a ) _ - 1 ，1 ) ，对于v ( c ) 中的任意子集合 s ，令f ( s ) _ 。s ，( u ) 定义1 1 【2 1 对任意的钞v ( g ) ，满足：，( m ) l ，则称，是图g 的一个 符号控制函数记u ( ，) = f ( v ) = 口v ，( u ) ，称为符号控制函数，的权重 记( g ) = m i n w ( f ) l f 是图g 的一个符号控制函数) ，称为图g 的符号控制数 1 l 绪论 如果图g 的符号控制函数f ，满足：u ( ，) = ( g ) ，f 是图g 的仉函数 定义1 2 【3 】对任意的v y ( g ) ，满足：，( ( 钉) ) 1 ，则称f 是g 的一个符号全 控制函数记u ( ，) = f ( v ) = u ，( u ) ，称为符号全控制函数f 的权重记 y i ( a ) = m i n w ( f ) f 是图g 的个符号全控制函数 ，称为图g 的符号全控制 数 如果图g 的符号全控制函数f ，满足：u ( ，) = t ( g ) ，则称f 是图g 的t 一函 数 在上面两个定义基础上，本文引进了图g 的g 符号控制的定义，并得到 了q 一符号控制关于不同参数的界 定义1 3 对任意的v y ( g ) ，满足：，( m ) q ，其中一( + 1 ) q 6 + 1 ，则称 ，是g 的一个q 一符号控制函数记w ( f ) f ( v ) = 。y ，( 秽) ，称为符号控制函数 f 的权重记馏( g ) = m i n w ( f ) f 是图g 的一个g 符号控制函数) ，称为图g 的 g 符号控制数 如果图g 的g 一符号控制函数厂，满足：u ( ，) = 馏( g ) ，则称f 是图g 的馏。函 数 当q 为允许范围内某一确定的数时，则可以定义相应的符号控制数显 然，当g = 1 时，馏就是图的符号控制数；当q = 一( + 1 ) 时，对于任意图 g ，有百c a + 1 ) ( g ) = i g i ；当q = 5 + 1 时，对于七正则图和七拟正则图，有 嘭“( g ) = f a l ；而且容易知道：当g 一( + i ) 或q 5 + 1 ，任意图的q 符号控 制函数是不存在的 在本文中，对于图的g 符号控制数，主要讨论简单连通图，而对于非连通图g ， 记g 的各个连通分支为x 1 ，恐， 分别是定义在x d i = 1 ，2 ，m ) 上的 叼( x ) 一函数，则记，是所有五的并，显然，是图g 的馏( g ) 一函数，相应的每个控 制数之和就是图g 的g 符号控制数，所以只要研究简单连通图的g 符号控制数 即可 对于g 一符号控制的上界，通过定义上限口一符号控制数进行计算 2 1 绪论 定义1 4 图g 的上限g 一符号控制数聪= m a x w ( f ) i f 是图g 的一个极小g 符 号控制函数) 一个q 一符号控制函数厂是极小的当且仅当不存在g 一符号控制函数 夕厂使得g 2 f - l + 么8 v g - h - - 干1 一n ，n = i v ( a ) 1 ( 2 ) 4 1 ( g ) n 一m ，礼= i v ( c ) l ，m = i e ( g ) i ( 3 ) t 4 】 们) 辫 ，6 是图g 的最大度和最小度 另外，对正则图的符号控制数，有下面的结论： ( 4 ) 5 1 b o h d a nz e l i n k a 证明了三正则图的符号控制数的上界是警，并构造 了一个图满足这个界 ( 5 ) 6 o d i l ef a v a r o n 证明了除p e t e r s e n 图的所有正则图的符号控制数的上界 冬了3 n 对于图的符号全控制数，也已经得到了今几个重要结果，并且对满足某些结 3 l 绪论 果的图进行了构造这里也仅仅表述几个关于重要参数的符号全控制数： 对任意的图g ，有 ( 1 ) f 7 】对于任意图g t ( g ) 、石i 1 - i - 1 一n ，n = l 矿( g ) ( 2 ) t 7 】对于任意图g t ( g ) 2 一m ) ，n = i v ( g ) i ，m = i e ( g ) i ( 3 ) t 7 】对于任意图g 们，艇粉瑞茜精礼 其中a 万2 ，a ，6 是图g 的最大度和最小度 另外，对正则图的符号控制数，有下面的结论： ( 4 ) 【5 对于忌正则图g c g ，= _ 等p 舵学 t ! 丛塑囹 1 0 其中t 是一个正整数，则由( g ) = 2 t n ，得 ( g ) 之2 1 0 卜n 下面将要证明对于任意的整数n ，存在图g 满足：i v ( g ) i = 佗，而( g ) 能够 达到我们所求的界 显然，讯( 1 ) ：1 ，( 恐) ：2 ，即对于礼= 1 ，2 ，( ) 满足这个界当礼3 时，利用已经构造出的图风( 文献【4 】) ： 令t ：f 土学1 ，k 是一个包含t 个顶点完全图，耳i 是包含n t 个顶 点的空图，风i ：虬u 去二，对于任意的u 虬至少要与瓦= 中2 - m - 7 一- - 1 个顶点 相邻，则 l e ( 虬，灭= ) i 2 ( n t ) 8 2 两类基本符号控制数 因此 所以 即 l v v nk f 1 + 掣1 t = i k , i 1 七掣 1 + 掣 掣 k 的顶点可以构成坐2 丑个包含两个顶点的不同集合，并且每个集合至多与 聒中的一个顶点相邻( 每个集合中的顶点都与聒中的这个顶点栩邻) 定义函数，：y ( 风) _ - 1 ，1 ) ，令 f ( v ) = - 1 口矗一t ， 1 v 虬 显然，是图巩的一个符号控制函数，满足： y ( 驯硼瞅圳= 掣+ 2 ( 礼叫 且( 剐= 2 半卜礼 对于任意图g ，若 则有 由于 e ( g ) l 去( 6 1 v ( c ) l 一3 万丽丽) - i + v 孚1 + 8 1 圃v ( g ) i e ( 巩) i 丢( 6 1 v ( h ) i 一3 万丽丽) 9 2 两类基本符弓控制数 可以得到 ( 凰) 2 i + v q + 4 0 ( i e ( c ) f 一 ( 玩) , n + 2j v ( g ) d i v ( h n ) i u 定理证明完毕 定理2 2 对于任意图g ，有 仉( g ) n 一言m 1 p ( 。) ，m = i e ( g ) i ，佗= i y ( g ) 并且这个界是可达的 这里p ) 的定义取决于n ，即：当n 是奇数时，p ) 为奇数；当礼是偶数时， p ( n ) 为偶数 证明：依旧沿用在定理2 1 证明中介绍的符号由于，是图g 的7 s 函数，则由定 义知： l y ( u ) r la i n ( u ) nb l ( u a ) 由此 i ( u ) ha l i n ( u ) n b i = i e ( 以，j e 7 ) j u 6 at l a 即 2 l e ( g 【a 】) i i e ( a ，b ) i 因为 e ( a ，b ) i 2 ( n t ) 所以 i e ( g ) i i e ( g 【a 】) l + 【e ( a ，b ) i 3 ( 凡一t ) 由这个不等式，能够得到 亡 n - j 1 m 1 0 2 两类基本符号控制数 ( g ) = 2 一亿扎一；m 由于( g ) 与l y ( g ) l 的奇偶性一致，因此 郴) 卜善吲m ， 考虑长度为n 的圈图g ，由定理2 2 可知： 仉( g ) = t t - - 吾2 棚= 争 记y ( g ) = v l ，v 2 ，) ，定义函数，：v ( g ) _ 一1 ，1 ) ，令 ，c 钉t ，= _ 1 i ；- - o 。( m 们佗o 。d d3 3 ) ，, 显然，是v ( g ) 的一个符号控制函数，并且u ( ，) = n 一2 【詈j ，因此 ( y ( g ) ) 5n 一2 l 詈j 又由于 争一- - - n - - 2l - 三j 所以这个界是可达的 2 2 几类特殊图的7 1 相对于符号控制数，我们类似的定义了符号全控制数对于符号全控制数，也 得到了不少结果，在绪论中已经列举了几个重要的结论虽然已经得到了一般图 的符号全控制数，然而，很多图类的符号全控制数的值没有得到，在本文的这一部 2 两类基本符号控制数 佗= 2 k + 1 n = 2 k 证明：设f 是图g 的一函数，叩u ( 厂) = 7 t ( g ) 记p 和m 分别是在函数，下分 配1 和一i 的顶点集合，显然j p i + i 引= 佗由定义可知：任意u v ，( ( u ) ) 1 ， 故对u p ，有 ，( ( ) ) + ，( u ) = l p i i m i 2 而对v m ，有 - 厂( ) ) + f ( v ) = i p i i m i 0 从而 i p i i m l 2 所以 | p | i t 2 + n 引i t n - 2 i 因此 嘭( ) = f ( y ) ：i p i m i t 2 + n 1 i t n - 2 i 设g 是这样一个函数：将中的顶点i 丁2 + n 1 分配1 ，f 孚j 个顶点分配一1 ，显然g 是的一个符号全控制函数，由于厂是的t 一函数，所以 i 丁2 + ni l 丁n - 2i = 删) i 丁2 + n i - | t n - 2 即当几= 2 k + 1 时，1 ：( 风) = 3 ；当n = 2 k 时，y ：( 甄) = 2 完全图的t - 符号标注，如图2 1 所示： 1 2 3 2 ，、【 1 1 0 v 有 讯 图 全 完于对 3互理定 2 两类基本符号控制数 1 图2 1 ： 1 忌。，n = 3 ，4 ，5 ，6 的t 一符号标注 么姆念 弋念7 图2 2 - k 1 n = 2 ，3 ，4 ，5 ，6 的t 一符号标注 定理2 4 对于星图k 1 有 。f 2 n ：2 k - - i - 1 ， ( 虬，n ) = 【3 礼= 2 k 结论显然 星图k 1 礼= 2 ，3 ，4 ，5 ，6 的t 一符号标注，如图2 2 所示： 定理2 5 对于扇图蜀。有 帆卜n + 1 - 2 1 詈j 礼l 冀 n 4 证明：对于l ns4 ，容易验证： 7 ：( f 1 一) = 礼+ 1 2 l 詈j 当凡5 时，设，是r ，。的一个符号全控制甬数，对于任意的i ，在厂( 仇一1 ) ，( 饥) ， 1 3 2 两类基本符九控制数 ，( u 件1 ) r f l 最多只能有一个的值为- 1 ，且最多有f 詈1 个为- 1 ，否则，必有一点u ，便 得。 ，( ( u ) ) 0 因此 镌( r ，。) n + 1 2 詈 定义函数，7 ：y ( r ，n ) _ 一l ，1 ) ，若扎= 0 ，l ( m o d3 ) ，且扎4 ，令 八砌= _ 1 i = - l 。( 删m o d 3 ) , ，c 耽，= q + 1 ，我们通过以下构造，使得图g 满足这个界记t = 3 口符号控佑4 f 卓i 则 所以 因此有 t-i+学vi +4 (q+ i) n t 2 + t ( q + 1 ) n t 2 一q t ( g + 1 ) n 一( q + 1 ) t t ( t q ) ( q + 1 ) ( 扎一t ) 设k 是有t 个顶点构成的完全图，j 磊是有礼一舌个顶点构成的空图v ( 1 q ) 中的 每个顶点 至多连接t q 个空图j 磊中的顶点，而对于任意项点让v ( k n - d ， 恰好连接图甄巾的g + 1 个顶点 由于 一q ) ( q + 1 ) ( 佗一t ) 所以，这样构造是可行的南此得到图g ，g 是一个有扎个顶点，其中有n t 个 度为g + l 顶点的图，表示为g = k t a k , ：_ t 。 定义映射到图g 上的函数，：v ( a ) 一 - 1 ，1 ) ，y 如- f ： m ，= ( 2 q + 1 ) n - 2 m 1 定理证明完毕 定理3 3 对于任意图g ，顶点集为y ( g ) ，巧是图g 的最大度和最小度，则有 郴，f 器镒糟焖f 1 证明：设，是图g 的一个键( g ) 一函数，l y ( g ) l = n ，记a = u v ( g ) l f ( v ) = 1 ) b = y ( g ) a 1 y ( g ) j = mj aj = t ，则j 日j = n t ，所以 赁( g ) = l a l l b l = 2 t 一礼 对于五，口y ( g ) ，anb = 毋，则 e ( a ，b ) = u v l u ，v e ( g ) ，乱a ，v j e 7 ) 由于，是图g 的一个键( g ) 一函数，容易知道：对于任意的顶点u y ( g ) ，有 另一方面 帅】na i _ i mnb i q p 1 n a i + i n u 】n b i = f u 】i 6 ( g ) + 1 2 7 3 口一符号控佑0 因此 i v v m 半半= g 由于i n v 】na l 是一个非负整数，因此 帅 na i 学1 l e ( a ，b ) i = l p 1na i - - e l 鱼学1 ) v 6 b b 一 所以 i e ( a ，b ) i ( | - 华m 叫， 由于1 4 l ：t ，则存在一个顶点u a 至少与集合b 中的f ( 6 c z q 必1 ) ( - - 0 1 个项 点相邻，而至少与集合a 中f - 韭竺兰芸趣型1 + q 一1 个顶点相邻，因此 点相邻，而至少与集合中i 业= 窆；型| + 一1 个顶点相邻，因此 所以 ( g ) d g ( 让) 2f 剑兰竺兰掣1 + g 一1 鲤也掣型+ q - 1 由此不等式，并且t 和叼( g ) = 2 t 一礼均为非负的整数，因此 郴) 巡业端嵩鼎等垫 定理证明完毕 如果q _ 1 ，则僧就是符号控制数由上面的三个定理可以得到推论3 1 2 8 一 ! 望二笪量鳖型 一一 _ - _ _ - 一一一 推论3 1 【4 】对于任意图g ，礼= i v ( g ) i ，m = f e ( g ) i ，a ，6 是图g 的最大度和最小 度，有 ( g ) 2 f 兰粤卜佗 ( g ) 佗一丢m 们) 锵 当6 ( g ) = z x ( g ) = 七时，作为定理3 3 的特例，容易得到忌一正则图的口一符号控 制数 推论3 2 图g 是一个砖正则图，顶点集为y ( g ) ，i y ( g ) l = 死，则 叼( g ) 雨q 礼。 当g = 1 时，又可以得到七一正则图的符号控制数 推论3 3 【4 】图g 是一个怒正则图，顶点集为y ( g ) ，i v ( g ) i = 礼，则 仉( g ) 雨1 扎 3 2 忌一正则图的上限g - 符号控制r g 上面主要讨论口符号控制数的下界，下面我们着重讨论正则图的上限q 一符号 控制数，首先证明两个简单的引理： 引理3 1 设，是图g 的一个g ，符号控制函数，是极小的当且仅当对于任意的 顶点u v ，( u ) = 1 ，至少存在一个顶点珏m ，使得q ，【喇曼q + l 证明：专假设存在钉l v ，( u 1 ) = l ，不存在顶点u p l 】，使得q ，l u 3 q + 1 由于，是图g 的一个g 一符号控制函数，所以 ， 叫q + 2 3q - 符号控制 定义映射到图g 上的函数夕：v ( g ) 一 一1 ，1 ) ，如下： ，、l ，( u ，) g ( v ) 5 l l v l ， 口= 7 2 1 容易证明，g 也是图g 的一个口一符号控制函数，并且g f ，与，是极小的矛盾 乍假如存在g 符号控制函数g f ，则必有一个顶点t ，使得i ( v ) = 1 且 夕( u ) = - 1 ，由于至少存在一个顶点u m ，使得q 厂【u 】q + l ，则必有 夕( u 】 g ，矛盾 若，是图g 的一个g 符号控制函数，容易得到下面的结论： 引理3 2 设，是图g 的一个口一符号控制函数，对以任意的顶点v v ( g ) ：如果 d c ( v ) 一q 为偶数，则i v 】q + 1 ；如果d g ( 口) 一q 为奇数，则y v 】g 下面我们利用以上两个引理证明七正则图的上限g 一符号控制数的界 定理3 4 如果图g 是一个屉一正则图，顶点集为y ( g ) ，l y ( g ) l = n ，则有 以j 器n h ； r；t二k二薰2q ) kq 1 冗二三三二二：l 2 + ( + 一+ 一17 一。一 并且这个界是可达的 i , - f l t 月：设g = ( ve ) ，是图g 的r ：( g ) 一函数，记p = ( u v ( g ) v ( v ) = 1 ) ， m = y ( g ) p ，i y ( g ) i = 佗，i p l = p ，i m i = m 则 情况1 ：k q 为偶数 u ( g ) = “，( ，) = i p l f m l = 他一2 m 3 口一符号控制 否则 对于任意顶点t ，p ，由定义可以知道 如( u ) 丁k - q ，d 尸( ) 字+ g 厂m q 因此可以把顶点集p 剖分成字+ 1 个互不相交的集合只= 如p i d m ( v ) = t ) ， 其中 吲邗( i - 0 1 1 2 ，字) 则 k - q 2 p p = 肌 2l 肌 显然 字 i p t = 批p 】i m 忌 由引理3 1 ，对于任意顶点u p ，至少存在一个项点u m ，满足： q y u 】q + 1 而由引理3 2 ，对于任意的顶点v y ( g ) ，由于k q 为偶数，所以 y v 】q + l i i l 以上两条可以知道：对于任意的顶点v p ，至少存在顶点u m ，满足： ，= q + l 显然，对于顶点集p 的每个集合只，仅有集合p ：单中的顶点满足：， “】= q + 1 ， 3 1 3 g 一符号控佑0 因此对于每个顶点u p o ，至少存在一个的邻点属于尸_ 虹所以 2 通过这些不等式，得到 p o i 【岛，哗 i 字p 字 生：卫! = i = 2 气-、弋一、 礼2 a + m2 伽+ p i + p 字+ 仇 i = 0t = 1 s k + q + 2 p 字+ 喜p 等争时m ：m 七掣+ m ：墅孚幽m 毪一q毪一q 所以 m 万恧再菰j m 因此 r s q ：w ( f ) = r , - - 2 m 俨2 再m ：! 坌必生1 2 们 一七2 + ( 3 + q ) k q ” 下面依旧通过构造一个图g 来证明这个界是可达的 当k q 为偶数，等式r ! = 拦粼n 成立当且仅当以上证明过程中的 所有不等式的等号成立 当等号成立时。由于 p 。= i p o ，p 宁】i = t k + q p 字 因此，集合r 中的每一个顶点恰好与集合尸血中的一个顶点相邻；另一方面， 2 集合p l ：a 中的每个顶点与謇合p o 中k + 2 q 个顶点相邻，与集合m 中纽2 个顶点 3 2 3q - - 符号控制 相邻；而集合最尹顶点的度和为老。p 字，因此b ，恳，最争一l 巾没有顶点与集 合最手中的顶点相邻，由引理3 1 容易知道： p 1 ，恳，2 一l2 d 义凼为 i t m ，峰】l = m k 所以集合m 是独立集 由于 丁k - q p 字= m k ，l i f o ，峰】l - 警p 宁丁p 字，峰j l 2t p 宁 集合尸亭也是一个独立集由宇p 争= 后m 和加= 字p 譬知： p o2 ( p 虹2 一, d k 所以，我们可以在顶点集r 上构造一个( k 一1 ) 一正则图 图3 2 显示了当q = 2 时4 一正则图q 一符号标注的情况，定义函数f ：v ( g ) _ 一1 ，1 ) ，在函数，映射作用下黑点的映射值为l ；白点的映射值为一1 情况2 ：k q 为奇数 对于任意顶点v p 。由定义知 d m ( u ) 鱼二二兰二! ，d 尸( u ) 堡- = 二+ 口 否则 ，m q 因此可以把顶点集尸剖分成出2+ 1 个互不相交的集合只= u p d m ( v ) = i ) ，其中 吲铋( 待0 j l 2 ，拿) 3 3 3 q - 符写控制 则 图3 2 ：q = 2 ，惫= 4 r $ 一符号标注 显然 生二声 i p i = 惮，n i l m 七 = 1 由引理3 1 ，对于任意顶点勘p ，至少存在一个顶点u 嘲，满足： q ，【札】g + l 而由引理3 2 ，对于任意的顶点u y ( g ) ，由于忌一g 为奇数，所以 厂m q 3 4 阢 芈渤 = p 3q - 符。写j 空制 由以上两条可以知道：对于任意的顶点v p ，至少存在顶点 i t m ，满足： ，【u 】= g 显然，对于顶点集p 的每个集合只，仅有集合展芋中的顶点满足“让】= q 因 此对于每个顶点u p o ，至少存在一个的邻点属于妇所以 2 通过这些不等式，得到 p o l p o ，峰】i 生乒p 平 凡= fp t - 4 - m = p o + fp i + p ! = g 盟+ m -一_j， i = oi - = 1 一k + q + l p 毕+ 善2 仇+ m 群喜嘞+ m 后等+ m = 坠譬筹盟仇 所以 、 k q + 1 m 万可可瓤丽m 因此 r ：= u ( ，) = n - - 2 m n 一2 石r 干弋参军蒜礼 尼2 + q k + q 一1 2 万玎2 再丽丽q - i - 1 协 后2 + ( + 口) 七一 ” 下面依旧通过构造个图g 来证明这个界是可达的 当忌一g 为奇数，等式r ：= 再k 2 ( + 2 + q k 口+ ) 后q - = - 9 1 干i 佗成立当且仅当以上证明过程中的 所右不等式的笔导成寺 3 5 3 q - 符n 控制 当等号成立时，由于 p 0 _ 慨峰】l - ! 皇兰p 竿 因此，集合p o 中的每一个顶点恰好与集合中的一个顶点相邻；另一方面， 集合r = 乒中的每个顶点与集合p o 中蛙p 个顶点相邻，与集合m 中墨二乒个 顶点相邻；而集合尸半顶点的度和为k p 争，因此p l ，p 2 ，见芋一1 中没有 顶点与集合旦型三中的顶点相邻，由引理3 1 容易知道： p 1 ，p 2 ，2 12 0 义凼为 i m ，p 半】i = m k 所以由集合m 是独立集 由于 半p 半= m k ，怖，峰= 竽p 掣 集合峰也是一个独立集由生二乒p 与芦= 七m 和p o = 坠乒p 与乒知： p o2p 半一m ) 七 所以我们可以在顶点集岛上构造一个( k 一1 ) - 正则图 图3 3 显示了当口= 2 时，5 正则图r 口一符号标注的情况，定义函数，：v ( o ) _ _ ( 一1 ，1 ) ，在函数，映射作用下黑点的映射值为l ；+ 白点的映射值为- 1 定理证明完毕 显然，对于任意图g ，容易知道q 嵋，因此由推论3 4 和定理3 4 两个结论， 可以知道尼正则图的q 符号控制的范围 当q 为允许范围内某一确定的数时，则可以定义相应的上限符号控制数如 果q = 1 ，则r ：就是上限符号控制数容易得到图的r 口的上界因此由定理3 4 可 3 6 3 口一符弓控市0 以推出推论3 4 图3 3 ：q = 2 ，k = 5 r ：一符号标注 推论3 4 吲图g 是一个k 一正则图，顶点集为y ( g ) ，l y ( g ) i = 几，则 胚k 曩篡 参考文献 【i b o n d y j a ，m u r t y u s r g r a p h t h e o r y w i t h a p p l i c a t i o n s m n e w y o r k ：m a c m i l l a n ，1 9 7 6 【2 】d u n b a rj s i g n e dd o m i n a t i o ni ng r a p h s 【j 】g r a p h sc o m b i n ，19 9 5 ，l ( 6 ) ：31l 一 3 2 2 3 】b o h d a nz ，l i b e r e c s i g n e dt o t a ld o m i n a t i o nn u m b e ro fag r a p h j c z e c h o s l o v a k m a t hj ，2 0 0 1 ，5 1 ( 1 2 6 ) ：2 2 5 2 2 9 4 】z h a n gz ，x ub ，l iy e t a l an o t eo nt h el o w e rb o u n d so fs i g n e dd o m i n a t i o nn u m b e r o fag r a p h j d i s c r e t em a t h ，1 9 9 9 ，1 9 5 ( 1 ) ：2 9 5 2 9 8 【5 】b o h d a nz e l i n k a s o m er e m a r k so nd o m i n a t i o ni nc u b i cg r a p h s j d i s c r e t em a t h ， 1 9 9 6 ，1 5 8 ( 4 ) ：2 4 9 2 5 5 【6 】f a v a r o no s i g n e dd o m i n a t i o ni nr e g u l a rg r a p h s 【j 】d i s c r e t em a t h ，1 9 9 5 ，1 5 8 ( 4 ) ： 2 8 3 - 2 9 3 【7 】h e n n i n gma s i g n e dt o t a ld o m i n a t i o ni ng r a p h s j d i s c r e t em a t h ，2 0 0 4 ，2 7 8 ( 7 ) ： 1 0 9 - 1 2 5 【8 】l ux z al o w e rb o u n do nt h et o t a ls i g n e dd o m i n a t i o nn u m b e r so fg r a p h s j s c i c h i n as e ra ，2 0 0 7 ，5 0 ( 8 ) ：115 7 - 116 2 【9 】j a c o b s o nms ，k i n c hl eo nt h ed o m i n a t i o nn u m b e ro fp r o d u c t so fg r a p h s j a r s c o m b i n ，1 9 8 4 ，l8 ( 8 ) ：3 3 - - 4 4 【1 0 w a n gc ，m a oj ap r o o fo fac o n j e c u r