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

2 0 0 6 年上海大学硕士学位论文 摘要 在过去的三十多年里，随着计算机科学的迅速发展，图论也得到了飞速发展， 而控制数理论的研究是图论中发展最快的几个领域之一控制数理论能够快速发 展的主要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社 会网络等理论与实践中有着重要的应用背景随着研究的深入和应用的激发，各 种新的控制参数不断涌现其中图的函数( 全) 控制数就是( 全) 控制数的一类自然 推广由于函数的引入，致使利用函数性质来研究控制数成为可能目前，函数控 制数已成为图的控制理论中一个崭新而富有挑战的研究方向 由于，对于任意图，几乎所有的函数控制数的判定问题均是n p - , 完全的，所以 对它们的上下界进行精确估计以及图的结构性质的刻画是人们很感兴趣的问题， 这对于设计相应的近似算法有重要的实际意义本文主要研究了几类函数全控制 数，其相应的结果分为以下三部分： 第一部分，首先得到了完全图和完全偶图的上负全控制数( 巧( g ) ) ；接着建立 了5 _ j e 则图的上负全控制数紧的上界，并刻画了达到此上界的极图；此外，还给出 一类3 - t 则图使得上负全控制数与符号全控制数( w ( g ) ) 之差可以无限地大( 有 关结果被a r sc o m b i n a t o r i a 录用) 第二部分，建立了任意图的尼萧号全控制数( 碱。( g ) ) 的两个下界，这两个界 都蕴涵了以前得到的图的符号全控制数和多数全控制数( 嘛。，( g ) ) 在正则图上的 所有下界结果 第三部分，提出了符号全2 - 独立数( 磊( g ) ) 的概念，并建立了它在任意图上 的几个可达上界；另外，还建立了它在n ( 6 ) 阶和最小度d ( g ) ( 2 ) 的多部图上 的最好可能上界( 有关结果被u t i l i t a sm a t h e m a t i c a 录用) 关键词： 图；全控制函数；上负全控制数；爷号全控制数；符号全2 弛立数 2 0 0 6 年上海大学硕士学位论文 i i a b s t r a c t w i t h i nt h el a s tm o r et h a nt h i r t y ) , 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 r e rs c i e n c e g r a p ht h e o r yh a ss e e ne x p l o s i v eg r o w t h t h es t u d 3 7o fd o m i n a t i o ni n g r a p h si so n eo ft h ef a s t e s tg r o w i n ga r e a sw i t h i ng r a p ht h e o r yt h er a p i dg r o w t ho f d o m i n a t i o nr e s e a r c hi sa t t r i b u t a b l em a i n l yt oi t ss om a a t ya p p l i c a t i o n st oo t h e rs c i 一 一e n c e sa n dr e a lw o r l dp r o b l e m s ，s u c h 邮c o n i b i n a t o r i a lo p t i r n i z a t i o n ，c o d i n gt h e o r y 、 c o m p u t e rs c i e n c e ，c o n u n u n i c a t i o nn e t w o r k s ) m o n i t o rs y s t e ma n ds o c i a ln e t w o r k t h e o r y w i t hr e s e a r c h i n gd e e p l y , m a n yd i f f e r e n tt y p e so fd o m i n a t i o np a r a m e t e r s h a v es p r u n gu pr a p i d l y ( t o t a l ) d o m i n a t i n gf u n c t i o ni ng r a p h si st h en a t u r a lv a r i a t i o no f ( t o t a l ) d o m i n a t i o n t h u s ，i ti sp o s s i b l et os t u d yd o m i n a t i o ni nt e r m so f f u n c t i o n a lp r o p e r t i e s n o w a d a y s ，t h es t u d yo nd o m i n a t i n gf u n c t i o n si san e wa n d c h a l l e n g a b l er e s e a r c hf i e l di nd o m i n a t i o nt h e o r e y a sa l m o s ta l ld e c i s i o np r o b l e m so fd o m i n a t i n gf u n t i o n sa r en p c o m p l e t ef o r g e n e r a lg r a p h s ，i ti si n t e r e s t i n gt oi n v e s t i g a t eb o u n d so ft h o s ea n dc h a r a c t e r i z et h e s t r u c t u r eo fg r a p h s ，w h i c hi su s e f u lt od e s i g nt h e i ra p p r o m i x a t i o na l g o r i t h m si n t h i s p a p e r ，w em a i n l yi n v e s t i g a t es e v e r a lk i n d so ft o t a ld o m i n a t i n gf u n c t i o n si n g r a p h s ，a n dt h ec o r r e s p o n d i n gr e s u l t sa r et h ef o l l o w i n gt h r e ep a r t s ： i nt h ef i r s tp a r t ( c h a p t e r3 ) ，w ef i r s t l yo b t a i nt h eu p p e rm i n u st o t a ld o m i n a t i o n n u m b e r so fc o m p l e t eg r a p ha n dc o m p l e t eb i p a r t i t eg r a p h a l s o ，w ee s t a b l i s ha l l u p p e rb o u n do nr ( g ) o ft h e5 - r e g u l a rg r a p ha n dc h a r a c t e r i z et h ee x t r e m a lg r a p h s a t t a i n i n gt h eu p p e rb o u n d f u r t h e r m o r e ) w ee x h i b i ta ni n f i n i t ef a m i l yo fc u b i c g r a p h si nw h i c ht h ed i f f e r e n c er _ ( g ) 一w ( g ) c a nb em a d ea r b i t r a r i l yl a r g e i nt h es e c o n dp a r t ( c h a p t e r3 ) ，w ee s t a b i j s ht w ol o w e rb o u n d so nk - s i g n e dt o t a l d o m i n a t i o nn u m b e r ( 慌s ( g ) ) f o rg e n e r a lg r a p h s b ya b o v er e s u l t s ，w ei m m e d i a t e l y o b t a i nt h el o w e rb o u n d so n s ( g ) ) a n d 镌。，( g ) ) f o rr r e g u l a rg r a p h s ，w h i c hh a v e b e e ng o t t e nb yo t h e rr e s e a r c h e r s i nt h et h i r dp a r t ( c h a p t e r4 ) ，w ei n t r o d u c et h ec o n c e p to f s i g n e dt o t a l2 一 i n d e p e n d e n c e ( 。2 t ( g ) ) ，a n de s t a b l i s hs o m es h a r pu p p e rb o u n d sf o rg e n e r a lg r a p h s 2 0 0 6 年上海大学硕士学位论文 i i i f u r t h e r m o r e ，w eo b t a i nas h a r pu p p e rb o u n do na 轰( g ) f o ra nr p a r t i t eg r a p hw i t h o r d e rn 6a n dm i n i m u md e g r e e5 2 k e yw o r d s ：g r a p h ；t o t a ld o m i n a t i n gf u n c t i o n ；u p p e rm i n u st o t a ld o m i n a t i o n n u m b e r ；k - s i g n e dt o t a ld o m i n a t i o nn u m b e r ；s i g n e dt o t a l2 - i n d e p e n d e n c en u m b e r 原创性声明 本人声明：所呈交的论文是本人在导师的指导下进行的研究工作。除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 签名= 谚海超 日期：2 o 。年f 月日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容。 保密的论文在解密后应遵守此规定 签名：2 每超导师签名：鳓男 日期：， 竹s 年6 a 日 2 0 0 6 年上海大学硕士学位论文 第一章引言 在近四十年里，随着计算机科学的迅速发展，图论的发展也非常迅猛，其中图 的控制数理论是图论中发展最快的几个领域之一控制数理论能够快速发展的主 要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社会网络 等理论与实践中有着重要的应用 对图的控制数的研究最早可追溯到十九世纪中期当时有一种棋盘比赛，棋 赛的目的就是用某些棋子覆盖或者控制棋盘上的所有方格人们注意到了在棋盘 上如何放置最少几个皇后就可控制( 覆盖) 或占据所有的方格这样的问题，这就是 图的控制数问题的最初形式 在1 9 6 0 年前后，人们开始对图的控制数进行数学理论方面的研究所公认的 图的控制数理论是在1 9 5 8 年由b e r g e 和1 9 6 2 年由o r e 共同建立的1 9 5 8 年b e r g e 的图论专著中首次定义“控制数”这一概念( 虽然当时他用的是另外的名称) 而到 了1 9 6 2 年，o r e 的图论著作中，正式定义并使用目前一直沿用的控制数方面的术 语“d o m i n a t i n gs e t ”和“d o m i n a t i o nn u m b e r ”1 9 7 7 年，c o c k a y n e 和h e d e t n i e m i 在一篇报告中综述了当时已知的有关图的控制数的结果，并且首次使用符号7 ( g ) 表示图g 的控制数，此符号一直沿用至今此后的1 0 多年里，这一理论开始引起 人们的广泛关注并得到迅速发展，众多的研究者纷纷投入到控制数问题的研究中 来据1 9 9 0 年d i s c r e t em a t h e m a t i c s 出版的一期专辑( v o l8 6 ) 统计，截 至当时累计的文献就达到了4 0 0 篇随后控制数理论成为图论中一个重要的研究 热点，鉴于此理论的迅速发展，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 掣，“】在对此领域进行系统总结后，首次出版了两本关于图的控制数理论的专著 d o m i n a t i o ni ng r a p h s - - a d v a n c e dt o p i c s 和f u n d a m e n t a l so fd o m i n a t i o n i ng r a p h s ，其中在f u n d a m e n t a l so fd o m i n a t i o ni ng r a p h s 中引用了1 2 0 0 多个文献2 0 0 0 年，a m s 为d o m i n a t i n gs e t s ，i n d e p e n d e n ts e t s ，c l i q u e s 在分 类条目中专列了一项0 5 c 6 9 关于控制参数理论研究的全面进展可参阅f 2 2 ，2 3 1 随着控制数理论研究的深入和应用领域的拓宽，各种控制参数也不断涌现 到目前为止，控制参数种类已经多达几十种，其中，函数( 全) 控制数就是f 全) 控 制数的一类自然推广1 9 9 6 年，b a n g e 2 1 等引入了一类推广的图的控制数一p 一 2 0 0 6 年上海大学硕士学位论文 2 控制函数设p 是一实数集，函数，：v ( c ) 一p 称为图g 的p 一控制函数，如 果对每个点”v ( g ) ，有f ( n v j ) 三1 ，这里，n v = 扣i 扎 e ( g ) ) u 口 ： ，( m ) = 。f 叫，( u ) 图的p 控制数定义为： 弦= r a i n f ( v ) i ，是g 的p 一控制函数) 当p = o ：1 ) 时则是图的标准控制数；当p = 一1 1 ) 和p = 一10 ，1 时，则 分别是图的符号控制数和负控制数，其相关研究结果可参见文献f 9 ，1 0 ，1 2 ，1 3 ，1 9 ， 2 4 ：3 2 ，3 3 ，3 5 ，3 7 把上述定义中的，( m ) 1 改为，( ( 目) ) 1 就得到相应的 全控制数、符号全控制数和负全控制数它们的定义具体见本文第二章 目前，关于函数控制数贴切的应用背景几乎没有，不过在文献f 2 1 1 中h a r r i s 和h a t t i n g h 给出了关于负全控制数的一个有趣的研究背景例如，我们考虑某个 社会群体网络中的投票问题假定每个个体都有一张投票并持有最初的意见；进 一步，假设具有某种关系的个体之间的最终投票意见是互相影响的，且每个个体 对与之有某种关系的所有个体的投票意见的影响权重都相同如果与某个体有某 种关系的所有个体中持赞成票的个体数多于持反对票的个体数，那么该个体最终 就投赞成票；否则，就投反对票对此社会群体进行最初投票意见的分配，如果使 每个个体最终都投赞成票的话，则把此投票意见分配称为一致赞成分配在所有 的一致赞成分配中，我们主要对最初持赞成票或中立票的最少个体数目感兴趣 下面，我们对上述问题做个图论模型图中的点表示个体，两点之间的边表示 对应的两个个体具有某种关系给持赞成意见的顶点赋值+ 1 ，给持中立意见的 顶点赋值0 ，给持反对意见的顶点赋值一1 这样图中度大的顶点具有较大的“影 响力”图的负全控制数就是某个一致赞成分配中所有意见的最小可能和因此， 负全控制数也可以表示某个一致分配中持赞成票或中立票的最少个体数目，且与 之对应的意见分配可迫使每个个体最终都投赞成票 目前，对于函数全控制数的研究主要集中在以下几个方面： f 1 ) 确定各种控制参数的上下界，在一些特殊图上计算它们的值； ( 2 ) 寻找各种控制参数之间的关系； ( 3 ) 给出极端图类的结构性质的刻画； f 4 ) 讨论各种控制参数的复杂性问题，算法及应用问题 本文的主要工作是研究了几类函数全控制数，其相应的结果为以下三部分： 第一，首先得到了完全图和完全偶图的上负全控制数；接着建立了5 一正则图的上 2 0 0 6 年上海大学硕士学位论文 3 负全控制数紧的上界，并刻画了达到此界的极图；此外，还给出一类3 一正则图使 得上负全控制数与符号全控制数之差可以无限地大第二，建立了任意图的爷 号全控制数的两个下界第三，提出了符号全2 一独立数概念，并建立了它在任意 图上的几个上界；另外，还建立了它在多部图上的最好可能的上界 2 0 0 6 年上海大学硕士学位论文 4 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图均是无孤立点、无环无多重边的有限简单图凡是文中未加 定义的术语和符号，可参看文献f 3 ，2 2 1 为了叙述方便，我们首先引入一些定义和 记号设g = ( ve ) 是简单图，v ( g ) ，e ( g ) 分别表示图g 的顶点集和边集， g 的点的数目n = l v ( g ) 称为图g 的阶数如果图日满足条件v ( h ) v ( o ) 和 e ( h ) e ( o ) ，则称日为图g 的一个子图对s v ( a ) ，用a s 1 表示由s 导出 的子图 图g 中点x 的开邻域定义为n ( x ，g ) = jx y e ( g ) ，z 的闭邻域为 n x ，g 】= n ( x ：g ) u z 更一般地，对任意的义v ( g ) ，我们定义n ( x ，g ) = u 。；x n ( x ，g ) ，n ，g = n ( x ，g ) ux 在不引起混淆的情况下，上述符号可分别 简记为( z ) ，n i x ，n ( x ) 和n i x 我们称d ( z ) = j ( 。) 为点z 的度数，度数 为1 和0 的点分别被称为图的悬挂点和孤立点特别地，树中的悬挂点也叫叶 子分别用6 ( g ) 和( g ) 表示图g 的最小度和最大度图g 中度为奇数和偶数 的点分别称为奇度点和偶度点所有顶点的度都等于k 的图g 称为k - 正则图 在图g 中如果两个不同的顶点在g 中是不邻接的，则称它们是独立的如果点集 s v ( c ) 中所有点都是相互独立的，则称s 是g 的独立集 由n 个顶点构成的路和圈一般记作r 和c k 若图g 中的任意两个相异 点之间都有边相连，则称g 为完全图：几个顶点的完全图记作k 。用g = ( m ，k ；e ) 表示顶点集是u 叁1 k ，边集是 x v z ( o ) lz k ，y ，l i 0 ，至少存在一 个点u ( 口) ，使得，m 1 ，2 ) 类似地，图的符号全控制数和上符号全控制 2 0 0 6 年上海大学硕士学位论文 6 数即为： 霄( g ) = m i n w ( f ) l ，是g 的符号全控制函数 和 uc g ) = m a x w ( f ) 1 ，是g 的极小符号全控制函数) x i n g 4 5 等人引入图的多数全控制数( m a j o r i t yt o t a ld o m i n a t i o n ) 的概念函数 f ：v ( g ) 一卜1 ，1 ) 称为g 的多数全控制函数如果vc g ：5 - - - 4 s 的点，满足 ，m 三1 多数全控制数定义为： 镌。，( g ) = m i n w ( f ) f ，是g 的多数全控制函数) 最近，x i n g 4 6 等人还引入了肛符号全控制数( k - s i g n e dt o t a ld o m i n a t i o n ) 设 为正整数， 1sk 墨i v i 函数f ：v ( a ) 一 一1 ，1 ) 称为g 的k - 符号全控制函 数( k s t f ) ，如果v 中至少存在屉个点，满足f l y 1 一个k s t ff 是极小的，如 果对每个点口v ，不存在g 的一个k s t fg ，使得g f ：且g ( v ) 茎，( ) 图的 a 一符号全控制数和k 一上符号全控制数分别为； 以。( g ) = m i n w ( f ) i ，是g 的k s t f 和 r ：。( g ) = m i n ( t u ( ，) l ，是g 的极，j 、k s t v 显然当k = 掣 ，l v l 时，碱。( g ) 分别为多数全控制数和符号全控制数，而当 k = l v i 时，琏。( g ) 就是上符号全控制数 2 2 函数全控制数的主要结果 近些年来对上述各种函数控制参数的研究主要集中在界、判定问题的复杂性、 算法、各种参数之间的关系以及极图的刻画等方面下面我们给出相关的主要研 究结果 关于( 上) 全控制数方面的研究主要有以下结果： 定理2 2 1 ( 【5 ) 若g 是阶n ( 23 ) 的连通图，则m ( g ) 2 , 3 ，且此界是可达的 定理2 2 2 ( 2 5 ) 若g 为阶n 的连通图，最小度6 ( g ) 2 ，且g 岳 g ，g ，g ，c 1 0 ) 则m ( g ) 4 n 7 2 0 0 6 年上海大学硕士学位论文 7 定理2 2 3 ( 16 ) 若g 为阶n 的图，最小度6 ( g ) 3 ，则7 t ( 6 1 ) 7 n 1 3 下一个定理是文献 1 6 中的猜想，2 0 0 4 年分别被a r c h d e a c o n 等八位研究者 独立地解决了 定理2 2 4 ( 1 ) 若g 为阶n 的图，最小度6 ( a ) 23 j 则仉( g ) 蔓n 2 ；且此界是 可达的 最近，t h o m a s s e 和y e o 又得到了关于全控制数的一个新上界 定理2 2 5 ( 4 3 】) 若g 为阶礼的图，最小度d ( g ) 4 ；则m ( g ) 曼3 n 7 其他有关全控制数的研究成果可参阅文献【8 ，2 8 ，2 9 定理2 2 6 ( 1 7 ) 若g 为n 阶的连通无爪图，最小度为6 ( a ) ，则 i 掣，- z - 5 l ，2 ) ， r t ( g ) 悲， - 2 - 5 3 ，4 ，5 ) ， l ；， 若d 6 ， 止已外， r ( g ) = 2 ( 礼+ 1 ) 3 当且仅当( 7 9 1u9 2 i 若d 3 ，4 ，5 ) ，贝1 jr t ( g ) = 4 n ( d + 3 ) 当且仅当g 鼠或6 = 5 时g 户i 若5 6 ：则r t ( g ) = n 2 当且仅 当g ， 1u 吼：吼和，的构造见文献 1 7 下面介绍一些有关全控制数和上全控制数的复杂性方面的研究结果，我们首 先介绍n p 一完全理论中判定问题( d e c i s i o np r o b l e m ) 的概念一类问题，如果它 的每个实例都可以表述为用“是”或“否”来回答的形式的话，那么称之为判定问 题 定理2 2 7 ( 3 9 ) 对于一个给定的二部图或弦图g 和一个正整数k v i 判定 7 t ( c ) 是否成立是p 一完全的 定理2 2 8 ( 1 4 】) 对于一个给定的图g 和一个正整数七墨l v l 判定r t ( g ) k 是否成立是p 一完全的 关于( 上) 负全控制数和( 上) 符号全控制数的研究，给出下面主要结果： 定理2 2 9 ( f 3 8 】) 若g = ( v 1 ：k ，一，k ；f ) 为n 阶女_ 部图，22 ，则 百( g ) 22 击一n ， 且此界是可达的 2 0 0 6 年上海大学硕士学位论文8 定理2 2 1 0 ( 4 2 ) 若g 为n 阶3 - 正则图，则r _ ( g ) 曼5 n 7 ，等式成立当且仅 当g t 丁是一类3 正则图的集合，它的具体构造可参阅文献 4 2 定理2 2 1 1 ( 4 2 ) 若g 为n 阶4 正则图，则r ；- ( c ) s7 n 1 0 ，等式成立当且仅 当g ， ，是一类4 正则图的集合，它的具体构造可参阅文献 4 2 定理2 2 1 2 ( 5 0 ) 若g 为n 阶k 正则图，则 邢，2 慷滋差 且此界是可达的 定理2 2 1 3 ( 2 7 】) 若g 为礼阶图，则w ( g ) 五i 可+ 1 - n ，等式成立当且 仅当g 了 了是一类图的集合，它的具体构造可参阅文献 2 7 - 定理2 2 1 4 ( 【27 ) 若g 为n 阶图，最小度6 2 ，最大度a ；则 邢川髂端瑞渊h 且此界是可达的 定理2 2 1 5 ( 27 ) 若g 为n 阶图，边数为m 则w ( g ) 22 ( n m ) 定理2 2 1 6 ( 2 7 ) 若t 为n22 阶的树，l ( t ) 为所有叶子的集合，则w ( t ) 三2 ， 等式成立当且仅当每个点v ( v ( t ) 一l ( t ) ) 是奇度点且至少与( d ( v ) 一1 ) 2 个 叶子邻接 定理2 2 1 7 ( 【2 7 ) 若g 为n 阶女正则图，则 联哪 麓瓢豢 且此界是可达的 此外，文献4 0 1 中也给出了几乎正则图上u ( c ) 的上界 定理2 2 1 8 ( 4 2 ) 若图g 的所有顶点都是奇度点，则u ( c ) r ；( g ) 下面介绍一些有关符号全控制数和负全控制数的复杂性和算法方面的研究结 果，我们首先给出图的符号全控制数和负全控制数的判定问题形式： 2 0 0 6 年上海大学硕士学位论文 9 符号全控制数问题 实例：给出图g 和正整数k5i v ( v ) 1 问题：赁( g ) k 是否成立? 负全控制数问题 实例：给出图g 和正整数k s v ( c ) 1 问题：百( g ) k 是否成立? 2 0 0 4 年，h e n n i n g 证明了符号全控制数的判定问题是尸皖全的，而h a r r i s 和h a t t i n g h 证明了负全控制数的判定问题是p 一完全的 定理2 2 1 9 ( 27 ) 图的符号全控制数的判定问题是n p 完全的，即使对于二部 图或弦图也是成立的 定理2 2 2 0 ( 2 1 ) 图的负全控制数的判定问题是p 一完全的，即使对于二部图 或弦图也是成立的 此外，在文献 2 1 中h a r r i s 和h a t t i n g h 还给出了树上计算w ( t ) 和百( 丁) 的线 性时间算法 最后我们介绍一些有关多数全控制数和七一符号全控制数方面的研究结果 2 0 0 5 年，x i n g 等人研究了图的多数全控制数，并得到了下列结果： 定理2 2 2 1 ( 45 ) 对n 2 ，则 蒯t 耻k 臻兰 n ，m 为奇数 n ，m 为偶数 凡为奇数 n 为偶数 l 2 4，(， 一 f f l、j 一 m k 叩 n m 对 、j 542222 理定 i 一 叭 ，、 | | 、) 则 只 l 乙 w 一 砖 r 对 、， 54 ，l 3222 理定 2 0 0 6 年上海大学硕士学位论文 1 0 定理2 2 2 4 ( 4 5 ) 对n 3 ，则 碡一g ) ： 3 ：棚奇数。 l0 n 为偶数 定理2 2 2 5 ( 【4 5 j ) 若g 为扎阶斟，最小履和最大反分别为o 1 和则 ( g ) 茅n 定理2 2 2 6 ( 4 5 ) 若g 为n 阶图，最小度和最大度分别为6 和；且图中的点 都为偶度点，则 划t g ) 三等m 定理2 2 2 7 ( 4 5 】) 若g 为扎阶七_ 正则图( k 1 ) ，则 + 、l 等n ，k 为奇数， 钳g ) 2 葛2 k 。二i l + “：”一 且此界是可达的 2 0 0 5 年，x i n g 等人还对萧号全控制数进行了研究，并得到下列结果： 定理2 2 2 8 ( f 4 6 ) 对礼2 ，则 7 ：。( ) = 1 ，n 为奇数且 ； 0 ，n 为偶数且茎；： 3 ，n 为奇数且； ks 礼； 2 ，n 为偶数且； k 茎n 定理2 2 2 9 ( 【4 6 ) 对凡m 1 ，a 嚷。( 。) = 1 一n 2 一n 2 ， 3 4 m 为奇数2 - k 礼； m 为偶数2 - k 兰n ； m ，n 为奇数2 - n s ? t t + n ； m + n 为奇数且n 盎m + 礼 m ，n 为偶数且n k m + n 2 0 0 6 年上海大学硕士学位论文 11 定理2 2 3 0 ( 4 6 ) 若g 为n 阶r - a e 则图p 1 ) ，皿 f 7 ：。( g ) 【 r 为奇数 r 为偶数 下列结果由x i n g 等人和h a r r i s 等人独立地得到 定理2 2 3 1 ( 4 6 ) 对n 2 ，则 谎。( p n ) ：- 1 为奇数且皓学 l2 k n ，否则 定理2 2 3 3 ( 【4 6 ) 若g 为佗阶图 。( g ) 竺 n 为偶数且= ： 船= 他： 否则 最小度和最大度分别为621 和，则 ! 垒! 孚! ! 垒1 2 1 。 d + 则 吼 嘎孔 3 ： 蛋 卜 他 、恤 帅 肥 p 吨 例 理定 2 0 0 6 年上海大学硕士学位论文 1 2 第三章图的上负全控制数和后一符号全控制数 本章我们首先给出了完全图和完全偶图的上负全控制数的值；接着建立了5 一 正则图的上负全控制数可达的上界，并刻画了达到此界的图类；最后研究了任意 图的一符号全控制数的下界 3 1 图的上负全控制数 在介绍本节的主要定理之前，我们作以下准备工作： 设g = e ) 为礼阶的图，f ：v 一 - 1 ：0 ，1 ) 为g 上的一个极小负全控制 函数称，为g 上的r g ( c ) 一函数，如果训( _ 厂) 一e ( g ) 对 v ( e ) 和s v ( g ) ， 用s ( ”) 表示s 中与点口相邻的点集，且令f s ( ”) l ：如( ”) 对x v ( g ) ，且 xns = 口，令e ( x ，s ) = u v e ( g ) “x ， s ) ：e ( x ：s ) = l e ( x ，s ) 1 p ， q 和m 的定义分别为：p = u vi ，( u ) = + 1 ) ， q = vf ，( ”) = o ) ， m = 。v | f ( v ) = 一1 设i p | = p ：i q 义： m 因此，训( ，) = p m 此外，我们还给出下列定 p 】d q ( v ) = i ：d m ( v ) = j ) ， p qd p ( v ) = i ，d m ( v ) = j ) ， 口md e ( v ) = i ，d q ( v ) = n 目前，关于图的上负全控制数耳( g ) 的研究除了文献 4 2 中得到的结果，几 乎没有什么进展下面我们首先给出r t ( c ) 在完全图和完全二部图上的值下面 的引理可以从文献f 4 2 1 中得到 引理3 1 1 ( 4 2 】) 图g = ( k e ) 上的一个负全控制函数，是极小的当且仅当对 每个点v 且，( 口) o ，则存在一个点“( u ) 使得，m = 1 ， 定理3 1 1 对阶为亿( 2 ) 的完全图墨；，则r _ ( j ) = 2 证明：设，为上的一个耳( k 。) _ 函数，则p 0 根据引理3 1l ：对任意点v p ， 则存在一个点“( ) 使得， = 1 由于， u = ，( ) + 。( 。) 刊，) ，所以 阻 ， ， 和只q 尬 q 2 0 0 6 年上海大学硕士学位论文 1 3 。e ( ( 。) 一。) f ( w ) = 0y - n 为1 ，p = ，( u ) + 。；( _ v ( 。) 一。) f ( w ) 和，( 扎) s1 ，所 以，( u ) = 1 因此，e ( k 。) = w ( f ) = ，( 扎) + ，m = 2 定理证毕 定理3 1 2 对m ，三1 的完全偶图。，则r f ( 。) = 2 证明：设。= ( xuy ：e ) ，取= p nx ，p y = pny 设，为。上的一个 盯( 耳。) 一函数，则f k o 且b ，d 根据引理311 ：对任意点x p x ：则存 在一个点“( z ) = y 使得，m = f ( x ) = l ；对任意点y p x ，则存在一个点 u n ( y ) = x 使得，m = f ( y ) = 1 所以，r ( ，。) = 州( ，) = f ( x ) + ，( y ) = 2 定理证毕 下面的两个结果部分地解决了文献 4 2 中提出的问题我们先给出5 正则图 的上负全控制数的上界，并刻画了达到此上界的图类接着，构造了一无限图类使 得h ( g ) 怯( g ) 任意地大 证明定理3 1 3 之前，我们首先给出图类h 的构造：对整数h21 k 3 和 f 4 ，且满足5 f 一3 k = 4 h ，设g ，是一个5 - 正则图，它的顶点集为u 薹1 i a 。h 其 中i a i l = a i ，i = 1 ，2 ，5 ，这里的a 。是整数，且满足a 1 = k ，a 2 = 2 ，a 3 = 3 a 1 = 3 k ，a 4 = ( 5 1 3 k ) 2 和9 5 = 2 a a + 5 a 2 = 6 k + 5 i 此外，a 2 和也都是独立集 g z 的边集构造如下： a 1 中点之间连结k 条边，使得g a 是2 - i e 则图a 4 中点之间连结( 5 l 一3 k ) 4 条边，使得g 也 是l 正则图。a 中点之间连结1 2 k + 1 0 l 条边，使得g f a 是 4 一正则图 a 1 和a 3 之间连结3 k 条边，使得一l 中每个点恰好连结a 3 中的三个 点，而4 3 中每个点恰好连结a 1 中的一个点a 3 u a 4 和a 5 之间连结6 女+ 5 f 条 边，使得4 s 中每个点恰好连结a 3u4 4 中的一个点，a 3 中每个点恰好连结如 中的三个点，而a 4 中每个点恰好连结a 5 中的两个点最后，a 2 和如u a 。之 间连结5 f 条边，使得以2 中每个点恰好连结4 3u 山中的五个点，a 3 中每个点恰 好连结a 。中的个点，而也中每个点恰好连结a 2 中的两个点根据构造g 女f 就是5 一正则图，这些5 一正则图g ki 的全体记作h 定理3 1 3 若g 为礼阶的5 - 正则图，则耳( g ) 51 3 n 1 7 ，等式成立当且仅当 g m 证明：设，为图g 上的一个h ( g ) 一函数则玎( g ) = l p | _ l m l = p m 由定 义得，对任意点v v ，d q ( v ) 4 2 d u ( v ) 和d p ( v ) d v ( 口) + 1 1 否则， 2 0 0 6 年上海大学硕士学位论文1 4 ，m 1 因此可以把p ，q 和m 分别划分为以下集合 p q u m t i u p 】d q ( v ) = i ，d m ( v ) = j ，0 js2 ：0 。s4 2 j ) u qd p ( v ) = id m ( v ) = j ：0 j 墨2 ，+ l 。s5 一j ， u md 尸( 归。d q ( 叫司osjg l 孚i 墨5 一j ) 且令i 嘞i = p i j ，! q 巧i = 和i i = ”则 p = p o o + p o l + p 0 2 + p l o + p l l + p 2 0 + p 2 1 + p 3 0 + p 4 0 g = q l o + q 2 0 + 啦! + 的0 + 如】+ 驰2 + q 4 0 + 9 4 i + q s o m = m 1 4 + m 2 2 + m 2 3 + ? t l 3 0 + 7 7 3 1 + m 3 2 + m 4 0 + 7 n 4 1 + m 5 0 此外，记p = p 0 2up 2 lup 4 0 ，q 7 = q l ouq 2 1uq 3 2 ，m 7 = 尬4ua 如2u 飓o ，显 然，每个点 p 7ue 7um 7 在，下是g 的临界点，即，m = 1 ；而对每个点 ( v p 7 u q 7 u m ，) f l y 】2 通过计算边数e ( 只q ) ，e ( q ，m ) 和e ( 只m ) ，我 们立即得到下列等式 p l o + p l l + 劫2 0 + 2 p 2 1 + 3 ：0 3 0 + 4 p 4 0 = e ( p ，q ) 5 q 一( 4 q l o + 3 q 2 0 + 3 q 2 1 + 2 q 3 0 + 2 q 3 1 + 2 ( 3 2 + q 4 0 + q 4 1 ) ：( 3 11 ) q 2 1 + q 3 l + 2 啦2 + q 4 1 = e ( q m ) 4 m 1 4 + 2 m 2 2 + 3 r r 0 2 3 + f d , 3 1 + 2 m 3 2 十? t b 4 l p m + 2 p + p l l + p 2 1 = e ( 尸】m ) f 3 1 2 1 5 m 一( ? n 2 2 + 2 m 3 0 + m 3 l + m 4 0 + 驰1 + 9 3 1 + 2 啦2 + 啦! ) ( 3 1 3 ) 根据引理31 1 ，对每个点u p p 7 = p 0 0up 0 1up l ou 尸1 1up 2 0up 3 0 ，存在一个 点“u ( v ) 使得， 札 = 1 因此，对任意点u p p 7 ，总存在p 7u q 7um 7 中 一个点与v 相邻所以，我们可以得到 p o o + p o l + p l o + p t t + p 2 0 + p 3 0s 已( p p 7 ：p u q um ) e ( p p 7 ，p ) + e ( p p ，q u m 7 ) e ( 尸一p 7 ，p 0 2 ) + e ( p p 7 ，p 2 1 ) + e ( j d p 7 ，p 4 0 ) + e ( p p ，q 7 u m 7 ) ( 3 14 ) 2 0 0 6 年上海大学硕士学位论文 1 5 进一步，注意到对每个点w p 0 。，一定存在u 的一个邻点满足， “ = 1 ，也即， 让p 7 u m 若u p 7 ，则 至多邻接p p 7 中的两个点，但是，若u m 7 则 至多与p p7 中的三个点相邻因此，可记局。为集合蟛，和蜀：的不交并，其中 瑞。= z ，p 0 2 1d pp ，( ) = 3 ) ，蜀：= p 0 z 一瑞2 设i 蜀2 i = p ；2 ，则l 蜀! i = p 0 2 - - p r 因每个点口昂2 至少与m7 的一个点相邻，所以p j 2 墨e ( 弼2 ，m ，) 从而，有 = e ( p p 7 ：瑞2 u 踹) 曼3 p ：2 + 2 ( p 0 2 一瑞2 ) = 2 p 0 2 + p j 2 茎2 p 0 2 + e l ：p 0 2 ：m ，)( 3 1 5 ) 类似地，对每个点 p 2 1 ，在p 7uq 7um 7 中一定存在一个点与 相邻若 u p 7 ，则u 至多邻接p p 7 中的一个点，然而，若“q 7 u m 7 ，则 至多与p p 7 中的两个点相邻因此，可把岛2 划分为两个子集g ，= ”p 2 ，ld p _ p , ( u ) = 2 ) 和g ；= 岛- 一只。设i 足t i = p 1 2 1 ) 则lp j l = p 2 1 一p ：。因每个点口爿。至少邻 接q 7