（运筹学与控制论专业论文）图的函数控制参数.pdf

摘要 在过去的三十年里，图论中发展最快的领域也许是图的“d o m i n a t i o n ”的 研究根据实际背景的不同，现已定义的控制参数有几十种之多，而且随着研 究的深入和应用的激发，新的参数如雨后春笋，不断涌现 在本文中我们主要研究了以下两个部分：( 1 ) 三正则无爪图的负控制数和 符号控制数；( 2 ) 图的罗马控制数 第一章研究了三正则无爪图的负控制数和符号控制数，主要得到以下结 果： 定理1 2 9 三正则无爪图的上负控制数r 一( g ) l v ( a ) 1 推论1 2 1 0 若g 是三正则无爪图，则r 一( g ) r 。( g ) 定理1 3 6 若g 是连通的三正则无爪图，则( g ) ；n 第二章研究了图的罗马控制数，主要得到以下结果： 定理2 3 1 若g 是阶数为n 的连通图，则恤( g ) = v ( a ) + k 当且仅当 ( a ) g 中不存在点数为j 的点集s 至v 使得对任意的l j 一1 ， s j 扎一( ，y ( g ) + i ) + 句：j 七一l ( b ) 存在点集岛v ，1 i 岛i ，使得 i n i s o i = n h ( g ) + k ) + 2 1 s 0 1 推论2 3 2若g 是阶数为n 的连通图，女= m i n l ：3 s v l s l l ，1 【s 】i 一2 i s l = n ( 7 ( g ) + 2 ) ，则 r n ( g ) = 7 ( g ) + 定理2 , 3 3 若t 是阶数为n 2 的连通图，则垤( g ) = 7 ( g ) + 3 当且仅当( 1 ) 或( 2 ) 成立： ( 1 ) t = t t u t 2 + v - w 2 ，其中丑是健全的蜘蛛树，噩是病态的蜘蛛树，”。矿m ) ， 吨y ( 乃) ，且t 满足下列条件： ( 1 a ) 若正是p 2 ，则p 2 的任意顶点不能与五的头相连 ( 1 b ) 仇与啦不全是脚点 ( 2 ) t ：置u t 2 u t 3 + v 1 呓) ，其中丑，t 2 ，t 3 都是病态的蜘蛛树，v l y ) ， v 2 y ( 乃) ，选v ( t 2 ，y ( 乃) ，且t 满足下列条件： ( 2 a ) 若其中一个树是p 2 ，则p 2 的任意顶点不能与其它树的头相连 ( 2 b ) ”，与 ：不全是脚点 ( 2 c ) u ：与”a 不全是脚点 定理2 3 4 若g 是直径为2 的连通图，则g 或是罗马图或是满足( g ) = 2 7 ( g 1 一1 定理2 3 5 若g 是直径为2 的连通图且 t r ( g ) = 2 7 ( c ) 一1 ，则存在一个顶点 v v ( a ) 使得g u 是罗马图 定理2 3 6 若g 是任意的图，“是g 的任意一个顶点，h 是由g 在点u 上 粘一条长度为3 的路得到的图，则( h ) = 7 r ( g ) + 2 推论2 3 7 若g 是连通的罗马图，则h 也是罗马图 定理2 , 3 8 设g o 是阶数大于等于3 的图，u ，”v ( c o ) ，且d g 。( u ) = l v ( a 。) l 一1 ， d g 。( w ) = l _ 若g 是任意的罗马图，w 是g 的任意一个顶点，且h = g u g o + ， 则日也是罗马图 定理2 3 1 0 若g 是强罗马图，则任意7 集s 的每一个顶点”s 至少有三 个s - p n s 关键词：三正则图，无爪图，负控制数，符号控制数，罗马控制数，罗马 图 a b s t r a c t w i t h i nt h el a s tt h i r t yy e a r s c o n c u r r e n tw i t ht h eg r o w t ho fc o m p u t e rs c i e n c e ，g r a p h t h e o r yh a ss e e ne x p l o s i v eg r o w t h p e r h a p st h ef a s t e rg r o w i n g8 x e aw i t h i ng r a p ht h e o r yi s t h es t u d yo fd o m i n a t i o ni ng r a p h s t h ew i d ev a r i e t yo fd o m i n a t i o np a r a m e t e r st h a tc a n b ed e f i n e d ，a b o u t4 0 5 0d i f f e r e n tt y p e so fd o m i n a t i o nh a v eb e e nd e f i n e d i nt h i sp a p e r ，w cp a yo l l ra t t e n t i o nm a i n l yo nt h ef o l l o w i n gt w op a r t so ff u n c t i o n d o m i n a t i o ni ng r a p h s ：( 1 ) d e t e r m i n i n gt h eu p p e rm i n u sd o m i n a t i o nn u m b e ra n dt h e u p p e rs i g n e dd o m i n a t i o nn u m b e ri nac l a w - f r e ec u b i cg r a p h ( 2 ) d i s c u s s i n gs o m ep r o b h n s o nr o m a nd o m i n a t i o ni ng r a p h s i nc h a p t e r1 ，w ed i s c u s st h eu p p e rm i n u sd o m i n a t i o nn u m b e ra n dt h eu p p e rs i g n e d d o m i n a t i o nn u m b e ri nac l a w f r e ec u b i cg r a p h a n do b t a i nt h ef o l l o w i n gr e s u l t s t h e o r e m1 2 9t h eu p p e rm i n u sd o m i n a t i o nn u m b e rr 一( g ) o fac l a w f r e ec u b i c g r a p hg i sa tm o s t ；i v ( a ) 1 c o r o l l a r y1 2 1 0 i fgi sac l a w - f l e ec u b i cg r a p h ，t h e np - ( g ) r ，( g ) t h e o r e m1 3 6 e v e r yc o n n e c t e dc l a w - f l e ec u b i cg r a p hs a t i s f i e s7 s ( g ) ；n i nc h a p t e r2 ，w ei n v e s t i g a t er o m a nd o m i n a t i o ni ng r a p h s ，a n do b t a i nt h ef o l l o w i n g r e s u l t s t h e o r e m2 3 1i f ( ji sac o n n e c t e dg r a p ho fo r d e r 礼，t h e n7 兄( g ) = 7 ( g ) + ki fa n d o n l y i f ( a ) gd o e sn o th a v eav e r t e xs e ts vw i t h 【s l = js u c ht h a t l n i s i n 一( 7 ( g ) + i ) + 2 j ：j s 一1 f o r1 j k l - ( b ) t h e r ei sav e r t e xs e t 岛vw i t h1 i 岛i s u c ht h a t i w i l l i = n ( ，y ( g ) + k ) 十2 1 s o f c o r o l l a r y2 3 2 i fgi sac o n n e c t e dg r a p ho f o r d e rn ，a n d = m i n ：3 s kl l s 【l ，i n s l 【一2 i s 【= n 一( 1 ( g ) 十f ) ，t h e n7 r ( g ) = 1 ( g ) + 、 州 t h e o r e m2 3 3i fti sac o n n e c t e dt r e eo fo r d e rn 2 ，t h e n7 r ( g ) = 7 ( g ) + 3 i f a n do n l vi fe i t h e ro n eo ft h ef o l l o w i n gt w oc o n d i t i o n sh o l d s f 1 ) tc o n s i s t so fah e a l t h ys p i d e rn a n daw o u n d e ds p i d e rt 2w i t has i n g l ee d g e j o i n i n g 1 v ( 噩) a n dv 2 v ( 噩) ，s u b j e c tt ot h ef o l l o w i n gc o n d i t i o n s ： f l a ) i f 乃i sp 2 ，t h e nn e i t h e rv e r t i c e si np 2i sj o i n t e dt ot h eh e a dv e r t e xo f 正 ( 1 b ) 忱a n dv 2a r en o tb o t hf o o tv e r t i c e s ( 2 ) tc o n s i s t so ft h r e ew o u n d e ds p i d e r sn ，t 2 ，乃w i t ho n ee d g ej o i n i n gv l 矿( 五) a n d 却2 v ( 马) a n do n ee d g ej o i n i n g 吒v ( t 2 ) a n d 啦y ( 孔) ，s u b j e c tt ot h ef o l l o w i n g c o n d i t i o n s ： f 2 a ) i fe i t h e rt r e ei sp 2 ，t h e nn e i t h e rv e r t i c e si np 2i sj o i n t e dt ot h eh e a dv e r t e xo f o t h e rt r e e s ( 2 b ) v la n dv 2a r en o tb o t hf o o tv e r t i c e s ( 2 c ) ”：a n dv 3 en o tb o t hf o o tv e r t i c e s t h e o r e m2 3 4i fgi sac o n n e c t e dg r a p hw i t hd ( a ) = 2 ，t h e ngi se i t h e rr o m a n g r a p ho rag r a p hw i t h - y a ( g ) 一2 7 ( g ) 一1 t h e o r e m2 3 5 i fgi sac o n n e c t e dg r a p hw i t hp ( a ) = 2a n d 垤( g ) = 2 7 ( g ) 一1 ， t h e nt h e r ei sa v e r t e xv v ( a 1s u c ht h a tg ui sar o m a ng r a p h t h e o r e m2 3 6 i fgi s 虹l yg r a p ha n dui sa n yv e r t e xo fg ，t h e nt h eg r a p hh o b t a i n e df r o mgb ya t t a c h i n gap a t ho fl e n g t h3t ous a t i s f i e s1 r ( h ) = 7 r ( g ) + 2 c o r o l l a r y2 3 7 i fgi sc o n n e c t e dr o m a ng r a p h t h e n 日i sa l s or o m a n t h e o r e m2 3 8s u p p o s e g o i s a g r a p h w i t h l v ( a o ) l 3 ，u ，”v ( g o ) ，a n dd a o ( u ) = 1 v ( a o ) 1 1 ，d g ov ) 一1 l e tg b ea n yr o m a ng r a p ha n dwi sa n yv e r t e xo fg ，l e t 日= g u g o + t h e nh i sa l s or o m a n t h e o r e m2 3 1 0i fg r a p hgi ss t r o n g l yr o m a n t h e nf o re v e r y1 一s e tse a c hv e r t e x sh a sa t l e a s t t h r e es - p n s k e yw o r d s ：c u b i cg r a p h ，c l a w - f r e e ，m i n u sd o m i n a t i o n ，s i g n e dd o m i n a t i o n ，r o m a n d o m i n a t i o n ，r o m a ng r a p h ， 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者：尚卫苹l 勺2 孝 2 0 0 5 年4 月2 6 日f 引言 图的函数控制集是控制集概念的一类自然推广尽管其中某些概念目前人 们还没有发现它贴切的应用背景，但由于函数的加入，致使利用分析性质进行 处理成为可能，因此研究者们投入了极大的热情近几年来，人们在深化其理 论研究的过程中，不断拓广它的应用领域，使之成为图的控制数中一个崭新而 有趣的研究方向 d u n b a 等【3 ，5 1 引入图的负控制数( m i n u sd o m i n a t i o nn u m b e r ) 和符号控制数 ( s 协e dr a i n “sd o m i n a t i o nn u m b e r ) 的概念在文献 7 中，作者证明对每一个阶数 为n 的k 一正则图g ，若是偶数，则仉( g ) 雨n ；若是奇数，则( g ) 等 因此，对每一个阶数为n 的三正则图g ，l ( g ) ( g ) ；在文献f 8 】中，作者 证明对每一个阶数为n 的三正则图g ，f - ( g ) n 有关图的函数控制数的全面 研究进展可参看文献 3 ，4 ，5 ，9 ，1 0 ，1 1 在文献8 1 中，作者提出猜想：若g 是三正则图，则f 一( g ) sr ，( g ) 到目 前为止，此猜想还没有任何进展在此猜想的引导下，我们确立了三正则无爪 图的上负控制数r 一( g ) 的上界，即r 一( g ) ：l v ( a ) 1 因此对三正则无爪图有 f 一( g ) r 。( g ) 也就是说，对三正则无爪图上述猜想成立 1 a ns t e w a r t 【1 6 提出了罗马控制数恤( g ) 的定义，并证明了任意图g 满足 - y ( a ) t r ( g ) 2 1 ( g ) 图g 称为罗马图( r o m a ng r a p h ) ，若伽( g ) = 2 ，y ( g ) 在罗 马控制数方面人们比较感兴趣的问题是：找出更多的罗马图类；刻画i r ( g ) = 1 ( g ) + 的图的性质；确定一些特殊图的罗马控制数等 在第二章中，我们推广了命题2 2 1 2 和2 2 1 4 ，刻画 t a ( g ) = 7 ( g ) + k 的图的 性质；具体刻画了当7 r ( g ) = 7 ( g ) + 3 的树的情形；讨论了直径为2 的图；有一 个罗马图粘上一些特殊图后仍是罗马图等 因图的函数控制参数的确立是n p 一完全的，目前，关于图的函数控制数的 研究主要集中以下几个方面：( 1 ) 确立他们的上下界，计算一些特殊图的值； ( 2 ) 寻找不同控制参数之间的关系；( 3 ) 给出极端图类的刻画；( 4 ) 讨论其复杂 性问题及其应用问题 第一章三正则无爪图的函数控制 1 1基本概念 本文所讨论的均为无环无重边的简单图每个点的度均为三的图称为是三 正则图一个图称为无爪图，若它的任意点导出子图都不与k - s 同构设g 是简单图，我们用v ( o ) 和e ( c ) 分别表示图g 的点集和边集对每一个顶点 “v ，点。的开邻域n ( v ) 定义为 g ( v ) = “v ( a ) ：“ e ( g ) ) ”的闭邻域m 定义为 n v = n ( v ) t 3 u 更一般的，对任意的点集s v ，我们定义s 的开邻域和闭邻域分别是 n ( s ) = 川；v ( g ) s ：存在一点“s ，u 口e ( g ) ) ， 司= n ( s ) u s 设，是定义在点集y ( g ) 上的权函数，对任意的点集s v ( g ) ，我们定义 f ( s ) = ，( ”) ， y e s ，+ ( s ) = ，( 网) 特别的，对每一个顶点”y ( g ) ，我们记，4 ( ”) = ，( d u n b a r 等【3 ，5 】引入图的负控制函数( m i n u sd o m i n a t i n gf u n c t i o n ) 和符号控制 函数( s i g n e dd o m i n a t i n gf u n c t i o n ) 的概念函数f ：y ( g ) 一 - 1 ，0 ，1 ) 称为g 的负 控制函数，如果对每一点”y ( g ) ，有，+ ( ”) 1 一个负控制函数f 是极小的， 若对每一个满足 ( ”) 茎，( ”) v ”y ( g ) 的负控制函数h 均有h ：f 显然，一个 负控制函数f 是极小的当且仅当对g 中每一个满足，( ”) 0 的点”，总存在一 个点u m ，使得，4 ( ) = 1 图的负控制数( m i n u sd o m i n a t i o nn u m b e r ) 1 弋g ) 和 上负控制数( u p p e rm i n u sd o m i n a t i o nn u m b e r ) f - ( g ) 分别定义为： 1 ( g ) = 面n ，( g ) ) ：，是图g 的极小的负控制函数 r 一( g ) = m “ ，( y ( g ) ) ：，是图g 的极小的负控制函数) 函数，：v 一卜1 ，+ 1 ) 称为g 的符号控制函数，如果对每一点州i y ( g ) ，有 ，+ ( ”) 1 一个符号控制函数，是极小的，若对每一个满足 ( ”) ，( ”) v v ( g ) 的符号控制函数h 均有h = ，显然的，一个符号控制函数，是极小的当且仅当 对g 中每一个满足，( ) 0 的点u ，总存在一个点u 使得，+ ( u ) 1 ，2 ) 图的符号控制数( s i g n e dd o m i n a t i o nn u m b e r ) ( g ) 和上符号控制数( u p p e rs i g n e d d o m i n a t i o nn u m b e r ) r 。分别定义为： ( g ) = m i n f ( v ( g ) ) ：，是图g 的极小的符号控制函数) ， r 。( g ) = m a x f ( v ( g ) ) ：，是图g 的极小的符号控制函数) 3 5 1 2 三正则无爪图的上负控制数 下列简单的结果对我们的证明是非常有用的 引理1 2 1 一个负控制函数，是极小的当且仅当对每一点”v ( g ) ，f ( v ) 0 ， 总存在一个点“m ，使得广( ) = 1 设g 是连通的三正则无爪图，则g 的每一个顶点在一个三角形( t r i a n g l e ) 中对图g 中一个三角形c ，我们仍用c 表示该三角形的顶点集显然的，对 g 中任意两个不同的三角形c 和t 或者i c n t l = 0 ，或者l c f q t i = 2 设，是图g 的任意一个极小的负控制函数我们只需要证明，( v ( g ) ) ；1 v ( g ) i 若i y ( g ) i = 4 ，我们有g 竺确，此时结果是很容易验证的因此，在下 面的证明中我们假设i y ( g ) i 6 对i = 一l ，0 ，l ，我们记 k = 如v ( e ) ：，( u ) = 吐 g 中一个顶点v 称为是一个( n 。n o 、似。) 一点，若 i p 】n k l = n i ，i = 一1 ，0 ，1 对i = 1 ，2 ，3 ，4 ，我们记 只= u v ( c ) ：，+ ( ) = 吐 由于对每一个顶点”ey ( g ) ， ” 中恰好有4 个顶点，我们有 4 f ( v ( c ) ) = ，+ ( u ) u y f g ) 因此，我们得到 弓l 理1 2 2 ，( y ( g ) ) 一；( i f , i + 2 1 f 2 1 + 3 1 f h + 4 1 f 4 1 ) 设t 是g 中的一个三角形，我们称t 是一个独立的三角形( i n d e p e n d e n t t r i a n g l e ) ，若对g 中的每一个三角形e t ，我们有t n c ：0 对每一个顶点 ”y ( g ) ，我们称w 是单三角形( s i n g l e t r i a n g l e ) 顶点，若u 恰好属于g 中的一个 4 三角形若”v ( g ) 是一个单三角形顶点，我们用瓦表示包含”的唯一三角 形我们称t 是一个临界三角形( c r i t i c a lt r i a n g l e ) ，若t 中三个顶点的，一值分别 是一1 ，0 ，1 下面的结果是很容易得到的 引理1 2 3 若t 是g 中的一个临界三角形，则对于 t 且ue n ( v ) t ，我 们一定有 u f 1 且钍k 引理1 2 4 设g 中一个顶点“日，则v 是一个单三角形顶点进而，若u 是n ( v ) b 中唯一的顶点，则i i 也是一个单三角形顶点，并且咒是一个临界 三角形 证明设t = ”，x ，y ) 是g 中包含”的一个三角形u 是m t 中唯一的 顶点由于u 只，所以“， ，。，y v 1 注意到，+ ( z ) ，广( ) 2 由引理1 2 1 ，u ，x ，y 中有一个点属于f 1 因此，唯一的可能性是w 和u 都是单三角形顶点，且咒是 一个临界三角形引理得证口 设”和“是引理1 2 4 中定义的那类顶点我们称兀是与”相邻的临界三 角形，且记瓯= l 设 f l ( 4 ) = u 。e f 4 g ， f 3 ( 4 ) = 见n ( f l ( 4 ) ) 由引理1 2 3 ，我们得到 1 ( 4 ) 垦日 引理1 2 5l f 3 ( 4 ) 1 + 2 l f 4 i l n ( 4 ) | - 证明设 f 4 ( 1 ) = ”f 4 ：瓯n g = o 对任意的u 毋如 f 4 ( 2 ) = 毋：存在一点u p 4 ) 使得i gn 瓯l 一2 ) 则f 4 ( 2 ) 中的顶点是互相配对的，且与配对的两个顶点分别相邻的两个临界三 角形有两个共同的顶点进一步假设 毋( 1 ) = l ，w 2 ，w 。 ， 5 只( 2 ) 一 u l ，u 2 ，v l ，v 2 ， 且满足l g 。n g ，i = 2 ，1 曼i sb 设。；是f 4 ( 1 ) 中任意的一点注意到瓯，中与”，不相邻的两个顶点的f 一值 分别是一l 和o ，我们一定有i n ( c 。，) n 尼i 1 所以得到 l ( 瓯。) nf 3 1 + 2 l 瓯。i ，1 i a 设“ ，v i f 4 ( 2 ) ，l 茎isb 则( 瓯。u 瓯) 一 t “，吡) 垦门因此，我们有 1 n ( c 。u “) nf 3 i 十4 s l g ，u c q l ，1 s is 6 把上面两个不等式加起来，我们得到l 昆( 4 ) i + 2 i f , l 1f 1 ( 4 ) | 结论得证口 对于一个顶点”f 1 ，我们很容易的观察到l n ( v ) nf 3 1 2 对，而言，我 们称g 中一个单三角形顶点”f l 是一个不理想的顶点( u n d e s i r a b l ev e r t e z ) ，若 l ( ”) n f 3 i = 2 且m ) n r = 0 我们称g 中一个单三角形顶点”f l 是一个理 想的顶点( d e s i r a b l ev e r t e x ) ，若l ( u ) n 玛i = 2 且l ( 孔) nf l l 1 引理1 , 2 6 设g 中一个顶点v f 1 若l n ( v ) nf 3 i = 2 ，则”是一个单三角 形顶点，且对，而言，”或者是一个不理想的顶点或者是个理想的顶点进一 步，我们一定有 ( a ) 对，而言，若”是一个不理想的顶点，则f ( v ) = 1 ，且存在一点z 已 使得f ( x ) = o ； ( b ) 对，而言，若”是一个理想的顶点，则存在某一点y ) nf l 使得 ( 扣，w ) ) n f 3 = n ( v ) n f 3 证明设g 中一个顶点v r 满足i y ( v ) nf 3 l = 2 又设c 是包含”的一个 三角形由于”f l ，u 或者是一个( 0 ，3 ，1 ) 一点或者是一个( 1 ，1 ，2 ) 一点 若”是一个( 0 ，3 ，1 ) 一点，则对每一个顶点“a ，我们有广( u ) 2 所以， l ( ”) n 毋i 1 ，矛盾因此，”一定是一个( 1 ，1 ，2 ) 一点 若c n u t 是非空的，则对每一个顶点u c ，我们有，+ ( u ) 2 ，并且l ( ”) n f 3 i 1 ，矛盾因此，我们一定有c n 让。= o 这表明”是一个单三角形顶点 现在假设n ( v ) = u ，文 ，其中f ( y ) = 一1 则c = l n u ，z ) ，且y 是一个单三 6 角形顶点由于，( ) = 一1 ，对每一个顶点。d ，我们有，+ ( 。) 冬2 ，因此，一定 有( ”) nf 3 = ，) 我们分下面两种情形讨论 情形1y f 1 在这种情形，i n v l n b l = 2 ，l ) nf l i 1 因此，对，而言，”是一个理 想的顶点进一步，( 似 ) n f 3 = n ( v ) n f 3 = “，。) 因此，在这种情形中( b ) 成立我们可以观察到，在这种情形，对，而言，y 不是一个理想的顶点 情形2ye 最 在这种情形下，由于y vznf 2 ，y 一定是一个( 1 ，0 ，3 ) 一点因此，( ) = 1 不失一般性我们假设，( “) = l 和，( z ) = 0 情形2 1 存在一点w ( 如，。) ) ) 使得w f 1 若，w x f ( g ) ，设。是( ) m z ) 中唯一的点由于，+ ( ”) = 1 ，( “) = 1 ， ，( z ) = o ，4 ( “) = ，。( 。) = 3 ，我们一定有，( ) = 1 和，( z ) = 一1 这表明，+ ( 。) 墨2 ， 且( 似”) ) nf 3 = n ( v ) n 玛= “，z ) 则对，而言，v 是一个理想的顶点在这 种子情形中( b ) 成立我们知道，在这种子情形中，则对，而畜，w 也是一个 理想的顶点，且满足咒n 咒= u ，z 1 f 3 若”u 与w x 中恰好有一个是g 中的边，则w 是g 中一个单三角形顶点 由于，4 似) = 1 ，( u ) = l ，f ( z ) = 0 ，4 ( u ) = ，+ ( z ) = 3 ，我们一定有，) = l 和 ，( 死) 1 这表明咒几f 3 = o ，且( 似 ) ) nf 3 = n ( v ) nf 3 = “，。 则对，而 言，”是一个理想的顶点在这种子情形中( b ) 成立我们知道，在这种予隋 形中，对，而言，w 不是一个理想的顶点 情形2 2n ( t o ) n 日= o 在这种子情形中，”是一个不理想的顶点由于，( ”) = 1 和，( 。) = 0 ，这表 明( a ) 成立 口 引理1 27 存在一个极小的负控制函数g 使得g ( y ( g ) ) = ，( v ( g ) ) ，且对9 而 言，g 中不存在不理想的顶点 证明对，而言，若g 中不存在不理想的顶点，我们不需再证否者，对， 而言，设bcv ( g ) 是不理想的顶点的集合由引理26 ( a ) ，对任意一个不理想 的顶点u b ，我们有，( ”) 一1 ，且存在一点”+ el 使得s ( v + ) = 0 设 b + = + ：veb ) 我们用下面的方法定义一个新的函数9 ：v ( a ) 一 一l ，0 ，1 9 ( v ) ，( ) ，若 v ( c ) ( b u b 。) o ，若v b ， 1 ，若 b + 显然，9 ( y ( g ) ) 一，( y ( g ) ) 由于，是图g 的一个极小的负控制函数，且对任意 一点u b 满足) nf 1 一o 所以g 也是图g 的一个极小的负控制函数因 ，是一个极小的负控制函数，由引理1 2 1 ，对g 中任意满足，( ”) 0 的点”，存 在一点“n v 】使得，( “) = 1 下面两个有利的事实 f l v ( a ) ：9 + ( ) 一1 ) 与 v ( c ) ：，( ) o ) = v ( a ) ：g ( ) o ) 是显然的因此，对任意一点”y ( g ) 满足9 ( u ) 0 ，存在一点u m 使得 9 + ( “) = 1 再由引理1 2 1 ，9 是一个极小的负控制函数我们知道，对g 而言， g 中不存在不理想的顶点结论得证 口 由引理1 2 7 的结论，下面我们不妨假设，是图g 的一个极小的负控制函 数，且对，而言，g 中不存在不理想的顶点 引理1 2 8i 且l i f a i + 2 1 f , i 证明对，而言，设_ d 是g 中理想的顶点的集合设 d + = ， d ：i 已n i = 2 ， 且 f 1 ( 3 ) = u 扣，。 d 口， ) r 由引理26 ( b ) ，对任意一点”d f l ( 3 ) ，存在某一点”m ) n ( f l d ) 使得 ( h ，) ) n 昂= n ( v ) nf 3 ，在这里i n ( v ) nf 3 l = 2 设 日( 2 ) = v ，u 7 ：目d f l ( 3 ) 容易验证r ( 2 ) ，f l ( 3 ) 和f l ( 4 ) 是互不相交的集合进一步记 r ( 1 ) = f l ( f l ( 2 ) uf l ( 3 ) uf l ( 4 ) ) 由理想的顶点的定义，引理1 2 6 ( b ) 和引理1 2 5 ，我们有 f 1 ( 1 ) i l ( 蜀( 1 ) ) n 岛i ； f 1 ( 2 ) i = l v ( 日( 2 ) ) n b j ； l n ( 3 ) l = i ( 日( 3 ) ) nf 3 i ； f 1 ( 4 ) l l n ( f t ( 4 ) ) nb i + 2 i f 4 | 因此可得 f l i l ( f 1 ) nf 3 i + 2 l f 4 1 由引理1 2 1 ，我们有l ( f 1 ) f lf 3 i = l 乃l ，结论得证 口 结合引理1 , 2 2 和引理t 2 8 ，可得，( 矿( g ) ) 冬 i v ( g ) 1 我们得到本节的主要结 果如下： 定理1 2 9 三正则无爪图的上负控制数f - ( g ) ；i v ( a ) 1 我们下面构造一个图说明定理1 2 9 的界是最好可能设是一个正的偶 数，我们构造一个阶数为n = 3 k 的三正则无爪图如下 v ( c ) = 孔：l i 2 k u 轨：l i 七 和 e ( g ) = 且u 如u e 3 ， 满足 蜀= x l x 2 ，x 2 2 3 ，x 2 kl x 2 k ，。2 k z l ) ， 9 e 2 = y i x 2 i 一1 ，y x 2 i ：1 墨i 埘 昂； 。，。g 。：l 茎z ；) 我们定义图g 的一个负控制函数，如下： ，( 劬) 一1 若v = y 2 il ，1 茎i 茎： 0 若u = y 2 ；，1 ， l 若u = 戤，1 i 2 k 容易验证，对任意一点”y ( a ) 满足，+ ( ”) 1 因此，时图g 的一个负 控制函数进一步可验证对任意的i ，l i ，我们有，+ 慨) = 1 由引理1 2 1 ， ，是一个极小的负控制函数 ，( y ) = i v ( a ) i 是显然的由定理1 2 9 ，得到 r 一( g ) = j l v ( c ) 1 由文献【7 得到，对任意的三正则g 满足r 。( g ) 2 ( g ) i i v ( g ) i 我们得到 如下的结果 推论1 2 1 0 若g 是三正则无爪图，则r _ ( g ) n ( g ) 定理1 , 2 1 1 若g 是三正则无爪图，且g 中每个三角形都是独立的，任意两 个三角形c 和t 满足l e ( c ，t ) l 茎1 若g 没有割边，则r 一( g ) = i v ( g ) i 证明设i y ( g ) i = n = 3 k 对1 i k ，收缩每个三角形g 为一个点矗得到 一个新图，则l v ( a 。) f = ，) ，且g 是一个三正则图若g 没有割边， 则g 也没有割边也就是说，g ，有完美匹配m ，因此，若翰m ，则在g 中 两个三角形q 和吗可以配对对任意对应匹配边z t m 的吡q e ( g ，q ) ， 令，( q ) = 一1 ，( ) = 0 ，其它2 个顶点的，一值定义为1 容易验证，是一个 极小的负控制函数，且f ( v ) = j l v ( c ) 1 由定理1 2 9 ，对任意的三正则无爪图， 1 1 一( g ) ；i v ( c ) 1 因此有r 一( g ) = i v ( c ) i 口 定理1 2 1 2 若g 是三正则无爪图，且g 中每个三角形都是独立的通过收缩 每个三角形为一个点，得到一个新图g 若g 有完美匹配，则r ( g ) = i i v ( g ) i 证明类似定理1 21 1 可证 1 0 1 3三正则无爪图的符号控制数 定理1 3 1 1 】若g 是阶数为n 的三正则图，则( g ) ；n 定理1 , 3 2 【6 若g 是阶数为, 且不同于p e t e r s e n 图的三正则图，则( g ) ；n 命题1 , 3 3 【6 】若g 是阶数为n 的三正则图，则( g ) = n 一2 n ( g 2 ) 其中o ( 日) 表示日的最大独立集的数目 引理1 3 4 若g 为直径小于3 的三正则图，则g 2 是一个完全图因此 n ( g 2 ) = 1 ，贝4 仉( g ) = 几一2 0 ( g 2 ) = n 一2 若c 为直径小于3 的三正则无爪图，则对每一个点w v ，i 。川8 因此 1 g l 茎8 若g 为阶数等于8 的三正则无爪图，那么g 的每一个三角形都是不独立 的这样的图只有一个，即 v ( c ) = u 1 ，7 3 2 ，) e ( c ) = 如l 2 ，“0 1 v 3 ，4 j 2 v 3 ，v 2 v 4 ，7 j 3 v 4 ，v l v 5 ，v 4 v 8 ，v 5 v 6 ，v 5 研，v 6 v 7 ，v 6 v 8 ，”7 8 但此图的直径为3 ，不满足引理的条件，即图的直径小于3 所以若g 为直径小 于3 的三正则无爪图，则i g l 6 ，由引理1 , 3 3 ( g ) = n 一2 ，我们得到仉( g ) 茎；n 引理1 3 5 设g 为直径至少为3 的三正则无爪图则存在两点“， v ( c ) 满足d a ( u ， ) = 3 且l 2 【 “， 州s1 3 定理1 3 6 若g 是连通的三正则无爪图，则仉( g ) s ；n 证明通过上面的讨论，下面只需要对直径至少为3 的连通的三正则无爪图 来证明对每一个点”v ，用n i v 和n 。i s 】分别表示与点”距离最多为i 的点 的集合和到s 中某个点距离最多为i 的点的集合我们将用下述算法构造一个 集合： s e tm 一：扣) ，是g 中任意一个点；s e tv ：= v 2 【m 1 ； w h i l ev 0d o c h o o s e v n 3 m 】v iva r b i t a r i l y ；s e tm ：= mu u ) ； 当程序终止时，m 中任意两点间的距离至少为3 ，因此m 是g 2 的独立 集因g 是三正则无爪图，由引理1 3 3 ，第一次选取两个顶点z ，y v ( v ) 满足 d v ( x ，y ) = 3 且f n 2 i x ， s1 3 ，选取z ，y 以后，我们最多去掉1 3 个顶点从第 二次开始，在以后每选取一个顶点”，我们最多去掉6 个顶点因”至少有一个 邻点和一个距离为2 的点已经被去掉因此， 进而有 i m i 下n - 1 因n 是偶数，我们得到i m i i n 所以 ( g ) = n 一2 n ( g 2 ) n - 2 i m i n 一2 ；s ；n 口 定理1 3 5 的界是最好可能下面我们构造一个阶数为6 的三正则无爪图如 下： e ( g ) = = z l 2 ，x l x 3 ，x 4 x 5 ，x 4 x 6 ，x 5 x 6 ，z 1 。4 ，z 3 2 5 ，z 2 2 6 ， 我们定义图g 的一个符号控制函数，如下： m ，= 三。鲻。 容易验证，( y ) = 4 = ；n 第二章图的罗马控制数 2 1基本概念 设g 是简单图，v ( g ) 和e ( g ) 分别表示图g 的顶点集和边集，n = v ( a ) 记作图g 的阶数图g 中任意点”的开邻域定义为n ( v ) = u v ：u u e ” 的闭邻域为m = n ( v ) u 如) 若s 是v 的一个子集，我们定义s 的开邻域为 n ( s ) = u 。s n ( v ) s ，s 的闭邻域为n s - n ( s ) u s 设”s v 若n u 】n s = ”) ，点u 称为点”的s 一私邻域点，简记为 s - p n 我们定义m ( ”，s ) = m n s p ) 为点”的s 一私邻域定义e p n ( v ，s ) = m ( ”，s ) 一 ” 为点”的s 一外私邻域因此集合e p n ( ? 2 ，s ) 包含点”的所有属于 v s 的s - p n s 设点集合s v ，s 称为控制集( d o m i n a t i n gs e t ) ，如果对每一个点7 2 v ，或者 在s 中，或者u 至少邻接于s 的一个点也即n ( s 卜v 图的控制数( d o m i n a t i o n n u m b e r ) 1 ( g ) 定义为图