（基础数学专业论文）几类图的伴随多项式及色性.pdf

卜 几类图的伴随多项式及色性 中文摘要 在1 9 7 8 年，c h a o 与w h i t e h e a d ( 2 ) 给出了一个图的色唯一的定义一一是不存在其 它图与它有相同的色多项式。用p ( a ，a ) 表示图g 的色多项式，如果p ( c ，a ) = p ( 日，入) ，则称g 和日色等价，记作g 一日。若对任意图日满足g 一日，都有g 垒 日，则称，图g 是色唯一的。到目前为止，诸多色唯一的图不断被发现，可参 考( 2 1 一4 1 ，f 7 1 ，8 1 ) 。 在1 9 8 7 年，刘儒英首次提出了图的伴随多项式的定义( f 2 5 】) ，并成功地运用它解决 图的色唯一性，它是通过考查一个图的补图来研究图的色唯一性。用h ( a ，z ) 表示 图g 的伴随多项式。如果h ( a ! z ) = h ( h ，z ) ，称图g 和日为伴随等价，简记为g 一_ 1 1 日。若对任意一个图h 满足g h 日且g 竺h ，则称图g 是伴随唯一的。图的色多项 式也是研究图的色性的基本工具之一。事实上，图g 和日是伴随等价的当且仅当其 补图虿和霄是色等价的；图g 和日是伴随唯一的当且仅其补图乏i 和万色唯一的。关于 方面的更多结论可参考( 5 】，【9 l 一【1 1 1 ，【1 4 1 ，【1 5 】，【2 3 】 【3 5 】) 。 本文主要运用伴随多项式的最小根，特征标，整除性，特殊分支以及分类讨论的方 法对以下图的补图的的色性与伴随等价性。 图镌( 佗一5 ，3 ) 是色唯一的当且仅当仃之i 0 ； ： 当n 7 ，佗9 ，1 2 时，图靠( 礼一2 ，3 ) 与矗( 4 ，n 一3 ) ，器( 1 ，佗一4 ) 是伴随等价的： 当n = r - i - t - i - 4 ，r ，t l 时，证明了露( r 1 ，) 的根大小排序。 关键词：色多项式，伴随多项式，特征标，伴随唯一，色唯一。 t h ea d j o i n tp o l y n o m i a la n dt h e c h r o m a t i c i t yo fs e v e r a lk i n d so f g r a p h s a b s t r a c t i n1 9 7 8 ，c h a oa n dw h i t e h e a d ( 2 ) d e f i n e dag r a p ht ob ec h r o m a t i c a l l yu n i q u ei fo n o t h e rg r a p h ss h a r ei t sc h r o m a t i cp o l y n o m i a l t h ec h r o m a t i c i t yo fg r a p l l si sd e n o t e d b yp ( a ，入) f o rg r a p hg t w o 伊a p h sg a n d 日a r es a i dt ob ec h r o m a t i c a l l ye q u i v a ，- l e n t ，d e n o t e db yg h s of a r ，al o to fc l a s s e s 静a p h so fc h r o m a t i cu n i q u e n e s sh a v e b e e nf o u n d e ds u c c e s s i v e l y , r e f e r i n gt o ( 【2 卜 4 】，【7 】，f 8 】) t h en o t i o no fa d j o i n tp o l y n o m i a lo ff i r s ti n t r o d u c e ，a n di nv i r t u eo fi t ，s u c c e e d e d i ns t u d yo fc h r o m a t i c i t yo fg r a p h sl i u 2 5 】i n1 9 8 7 ，w h i c hw a su s e dt oi n v e s t i g a t e t h ec h r o m a t i c i t yo fag r a p hf r o mi t sc o m p l e m e n t b yh ( a ，z ) w ed e n o t et h ea d j o i n t p o l y n o m i a lo fg i fh ( a ，z ) = h ( h ，z ) ，t w og r a p l l sga n dha r es a i dt ob ea d j o i n t l y e q u i v a l e n t ，d e n o t e db yg 一 h ag r a p hgi sc a l l e da d j o i n t l yu n i q u ei fg 笺h w h e n e v e r g 一 h a d j i o n tp o l y n o m i a lo fag r a p hl i k e w i s ei so n eo fb a s i ct o o l sf o r s t u d y i n gt h ec h r o m a t i c i t yo fg r a p h s a sam a t t e ro ff a c t ，t w og r a p l l sg a n dha r e s a i dt ob ea d j o i n t l ye q u i v a l e n ti fa n do n l yi ft h e w sc o m p l e m e n tg r a p h 召a n d 耳 s a i dt ob ec h r o m a t i c a l l ye q u i v a l e n ta n dg r a p hgi sa d j o i n t l yu n i q u ei fa n do n l yi f i t sc o m p l e m e n tgi sc h r o m a t i c a l l yu n i q u e m o r er e l a t e dr e s u l t sc a l lb ef o u n d e di n ( 5 1 ，【9 卜【1 1 】，【1 4 】，【1 5 】，1 2 3 一1 3 5 】) i nt h et h e s i s ，w ed i s c u s st h ec h r o m a t i c i t yo ft h ef o l l o w i n gg r a p h sm a i n l yv i at h e p r o p e r t i e so ft h ea d j o i n tp o l y n o m i a l s ，i n c l u d i n gi n j 2 1 i n 2 u ma d j o i n tr o o t s ，c h a r a c t e r ， d i v i s i b i l i t y , e s p e c i a lc o m p l e m e n t s ，c a t e g o r i z i n gd i s c u s s i o nm e t h o da n ds oo n w ep r o v et h eg r a p h 妒矗( n 一5 ，3 ) i sc h r o m a t i c a l l yu n i q u ei fa n do n l yi f 他21 0 ； w ep r o v et w og r a p h s 鑫( 佗一2 ，3 ) a n d 靠( 4 ，佗一3 ) ，繇( 1 ，佗一4 ) a r ea d j o i n te q u i v a - l e n t ，w h e nn 7 ，n 9 ，1 2 ； w ep r o v et h eo r d e ro fm i n i m a lr o o fo f 繇( r ，1 ，t ) ，w h e nn = r + t + 4 ，r ，t21 k e y w o r d s ：c h r o m a t i cp o l y n o m i a l ；a d j o i n tp o l y n o m i a l ；c h a r a c t e r s ；a d j o i n t l yu n i q u e ； c h r o m a t i c a l l yu n i q u e 目录 第一章引言 1 1 前言 1 2 伴随多项式的代数性质， 1 3 主要结果， 第二章诹丽= 丽的伴随等价与色等价图 2 1 前言， 2 2 主要结果及证明。 第三章磊雨= 丽i 的伴随性质 1 7 3 1 前言。1 7 3 2 主要结果及证明2 2 第四章繇( r 1 ，t ) 的能量与其伴随多项式的关系2 9 4 1 前言2 9 4 2 主要结果及其证明3 1 附录t 参考文献 致谢 个人简历 i 3 4 3 9 4 1 4 2 第一章 引言 1 1 前言 本文考虑的图都是有限无向的简单图。文中没有定义的等号与专业术语可参见【1 】。 用召，y ( g ) ，p ( g ) ，g ( g ) 与p ( g ，a ) 分别表示补图，顶点集，边集和g 的色多项式。 对于一个正整数后，y ( g ) 的一个划分a l ，a 2 ，九就叫做图g 的一个独立分划， 如果a 是图g 的非空独立集，j 黾m ( g ，七) 表示y ( g ) 的k 的独立划分数，则 p p ( a ，入) = m ( g ，后) ( k = 0 这里y ( g ) = 弘( 入) 忌= a ( a 一1 ) ( a 一2 ) ( a k + 1 ) 如果p ( 日，a ) = p ( g ，a ) ，则称g 和日是色等价的( 廿等价) ，记为g 一日。若 对任意与图g 色等价的图圩，都有g 名h ，则称图g 是色唯一( x 唯一) 。这些关 于色等价和色唯一的问题称为图的色性。在1 9 7 8 年，一日c h a o 和w h i t e h e a d 2 首先引 入x 唯一的概念。从那以后，诸多) ( 唯一的图都被找到f 3 ，7 ，8 1 。 若g 是一个p 阶图。若图g 的生成子图g o 的每个分支都是完全图，则称g o 为g 的 理想子图。若b ( a ，后) 表示g 恰有个p t 分支的理想子图的个数。注意到6 ( g k ) = m ( 虿，k ) ，其中k 为整数。图g 的伴随多项式可以定义如下： p - 1 h ( a ，z ) = 6 ( g ，后) 矿一知 k = 0 如果h ( a ，z ) = h ( h ，z ) ，称两个图g 和日是伴随等份的，简记为日一hg 。对任意与 图g 伴随等价的图日，都有g 兰h ，则称图g 是伴随唯一的。在1 9 8 7 年，刘儒英定 义了伴随多项式，同时继续用研究召的补图的伴随唯一性的方法来研究图( g 1 族的色 唯一性。从那以后，在研究图的色性方面，伴随多项式就成为一种基本工具。对最 新图族的色唯一性可参见 5 】， 9 卜【1 l 】， 1 4 】，f 1 5 】，2 3 】一【3 5 1 。 根据p ( a ，a ) ，h ( a ，z ) 的定义，可以到得下面的定理。 定m 1 ( 9 1 ) ( 1 ) h 一g 当且仅龋一。 ( 2 ) g 是x 唯一当且仅当伴随唯一。 若g 是一个p ( g ) = p ，q ( g ) = q 的图， ( g ，z ) = 铲( g ) 危1 ( g ；z ) ，a ( g ) 定义 为 ( g ，z ) 的最项低次数。为了简便起见，记 ( g ，z ) 为 ( g ) 与危1 ( g ，z ) 为 1 ( g ) 。 1 2 第l 章引言 用( g ) 定义h ( g ，z ) 的最小实根。对每一个t ，g ，用d g ( t ，) ( 或d ) ) 表示图g 中 点可的度。对两个图g 和日，gu 日定义为g 和日不相交的并。m h 表示仇个日不相 交的并。分别用和k 1 n 一1 定义完全图和佗阶的星图。船( 娲) $ d n g ( k 4 ) 分别表 示图g 的三角形和甄子图个数。g ( x ) j ( x ) 表示在有理数域上9 ( z ) 能整除，( z ) ，同 样9 ( z ) f ，( z ) 表示在有理数域上9 ( z ) 不能整除，( z ) 。用i f ( x ) ，9 ( z ) ) 定义为， ) 与g ( x ) 在实数域上的最大公因子。 现在，给出本文用到一些的图。 ( 1 ) q ，昂，分别表示p 阶的圈，路和完全图。记c = g i p 3 ) ，p = p p 眵22 ) 。 ( 2 ) 巩0 4 ) 表示q 的一个二度点与昂一2 的一个端点粘接后得到的图。 ( 3 ) 昂p 之6 ) 表示仍的一个二度点与d p 一2 的悬挂点粘接后得到的图。 ( 4 ) t ( h ，1 2 ，1 3 ) 具有一个三度占的口而满足t ( 1 l ，1 2 ，1 3 ) 一 = 只，u 最。u 局3 ( 1 3 1 2 之 z 1 ) 。记五= t ( 1 ，1 2 ，1 3 ) 1 2 3 1 2 l 和t = t ( 1 l ，1 2 ，1 3 ) 1 2 3 1 2 1 1 2 ) 。 ( 5 ) = 铝( r ，s ) ，擘( r ，s ) ，( n s ，t ) ) 。 ( 6 渺= 僻，孵，硼( r ，s ) ，蟛( r ，s ) ，孵( n 8 ，t ) 。 ( 7 ) ( = 【，蟹( ，_ ，s ) ，譬( ns ，z ) ) 在本文中，一些用到的佗阶图可参见下面的图1 。 命宁鬓 r 织镌 镌( r 8 ) 惦( r ，s )织( r l s ，t )谵 ：5 醴( r ，s ) ：r：s 酲( r ，s ) s t 簖( ns ，t ) 族 篇 r 一 s 厶( 嵌 ( r ，8 ，t ) 1 图1 ( 虚线表示长大于或等于1 的路) 砂族 t + 1t + o t 产? 1 、。? t + 1t + b u ( r ，8 ，t ，a ，b ) po代扩p汗ky q：l：纠q 令；厶 丫 醴 莎矿活p骶 1 2 伴随多项式的代数性质。 1 2 伴随多项式的代数性质 以下是本文用到的定义和引理。 3 定义1 。( 1 2 4 ) 图g 的一条简单路是指其内部顶点在g 中的度均为2 寝的路。若此简单 路的端点在g 中的度均小于3 则称其为图g 的一条内部路。 定义2 ( f 2 9 j ) 设图含2 度点a ，a b s a c 是s a 关联的边。删去点a 及其关联的边 并添加边b c ，称为收缩点a o 若两个图g l 与g 2 通过不断收缩2 受点后同构则称 图g l 与g 2 同胚。 定义3 ( 2 9 ) i 基取e i e 岭、，若在e 上相继插入4 k - - 度点，璇1 3 表示对图a 筢j z z e 进 行了惫剖分( 特别她，k = o 意味指未利分) ，+ 1 为边e 的剖分数。 定义4 似驯选取e t e ( g ) f 1 i 砂，肘e i 迸地亿一，蒯分亿1 4 ) ，将得到韵所 有忆阶为的同胚图族记为g n = g n ( 1 1 k i t ) 。定义 岛m ( g n ) = m a x z ( r ) l r g n 】， 风讯( g n ) = 1 i n z c r ) l r g n 将g n 中届m 。霉( a n ) 、风 n ( 岛) 对应厅f f 根极值分别记为m n z ( g n ) 、m 伽( g r 忭) 。易匀耵= 1 肘，4 m 凹( g n ) = 屏，伽( g n ) = p ( g n ) 。 定义5 ( f 3 9 j ) 设e = 删是图g 的任意一条边，图g 卑e 是如下图：g 蠢e 的点集 为( y ( g ) 一v l ，耽) u 钉，其l f 聋g ，边集为 e 7 l e 7 e ( g ) ，e 7 与d 1 和沈都不关联 u u v l u n g ( v 1 ) nn g ( v 2 ) 定义6 g 是具有个n 顶点，口条边的图，m 用表示图g 中三角形的顶点集合，m ( 0 表 示g 中覆盖顶点i 的三角形的个数如果图g 的度彦列为。如，那么 以，6 0 ( g ) = 1 ；b l ( g ) = 钐 例6 2 ：( 口：11 一苎霹+ 叫蚝) ； 。 忙1 俐6 3 ( g ) = q ( q 2 + 3 q + 4 ) 一 ( g + 2 ) 霹+ 霹一ed 奶一e ( t ) d + ( g + 2 ) 6 + n ( k 4 ) 其中，b o ( g ) ，6 1 ( g ) ，6 2 ( g ) ，b ( g ) 是h ( g ，z ) 的前一到四项系数。 引理1 1 伊，劬g 表示图，并且e e ( g ) ，那么 九( g ，z ) = h ( a e ，z ) + h ( a 球e ，霉) 如采e = 删不是图g 中任意三角形的边，那么 h ( a ，z ) = h ( a e ，z ) + x h ( g u u ，z ) 引理1 2 俾钏门肌( r ，z ) = z ( 危( 尸n 一1 ，z ) + 危( r 一2 ，z ) ) j 2 ，忍( c k ，z ) = z ( 九( c 一1 ，z ) + h ( c k 一2 ，z ) ) i r 到h ( d n ，z ) = x ( h ( d n 一1 ，z ) + ( d n 一2 ，z ) ) j 心， ( f k ，z ) = x ( h ( f n 一1 ，z ) + ( 晶一2 ，z ) ) 4 第1 章引言 引理1 3 俐当阮为得数厅批( r ) ，尼( g ) ， ( 上k ) ， ( r ) 黼低项分别是z 号，知学， 警z 号，z 孚；凯为奇数肘，别分男； 是：学z 孚，船n + 。x ，z 孚，孚z 孚。 弓理1 4 s , 9 j ) g 是具有个n 顶点，q 条边的图。图g 的第一特征标可以定义为： f 0 ， ，、 当g = 0 ， 甩( g 卜1 郴) 一f 6 1 ( 鼍。1 ) + 1 ，当g o l 五 图g 的第二特征标也可以定义为： ， r z c g ，= k c g ，一( b l 字) 一c 6 - c g ，- - 2 ) ( b 2 c g ，一( 6 1 罗) ) 一6 c g ， 弓理1 5 ( 硌2 6 j ) 如果有k 个分支g 1 ，g 2 ，g k o 那么 h ( g ) = i i 危( g i ) ，马= 马( g t ) ，o = l ，2 ) 很明显，r 2 ( c ) 是图g 的一个常量。对两个图g 和h ，如果h ( g ) = 危( 日，或危1 ( g ) = h l ( h ) ，则铂( g ) = 而( 日) ，( j = 1 ，2 ) 。 弓、理1 6 ( f 5 。9 | ) 如果g 是一个孔阶的连通图，则 以皿1 ( g ) l ，等号成立当且仅当g 筌r m 2 ) 或g 兰蹈； 俐r l ( g ) = o 当且仅当g 笺g ，工k ，死4 ) 或k l ； ( s ) n z ( c ) = - i 当且仅当g 且q ( g ) = p ( g ) ，g 笺r 或g 垒j 酊且g ( g ) = p ( c 1 + 1 阮臆l ( g ) = 一2 当且仅当g 妒且q ( c ) = p ( c ) + 1 和g 鲁k 4 且q ( c ) = p ( c ) + 2 ( 5 ) r i ( g ) = - 3 且q ( g ) = p ( c ) + 2 当且仅当g ( 弓、理1 一。f 2 6 3 5 ) 如果g 是一个n 阶的连通图，则 以j 如果r l ( g ) = 0 ，- 1 ，- 2 ，那a q ( g ) p ( c ) + l r z ( g ) i ； 例如果r 1 ( g ) = - 3 ，那么q ( c ) p ( g ) + i r i ( g ) + 1 1 ； 俐如果r z ( c ) s - 4 ，那么q ( c ) p ( c ) + i r z ( c ) + 1 1 定义7 ( 1 2 8 1 ) 如果h 是g 的一个分支且满足；1 3 0 h 、) = 8 刚称h 为g 的特殊分支- 弓、理1 8 ( f 1 5 。2 l 。s 2 | ) 以夕彳 p ( j + 1 ) p ( p k ) ，p ( c k + 1 ) p ( ( ) ，p ( d n + 1 ) 卢( d 。) i f 矽p ( t ( 1 ，1 2 ，1 3 ) ) - ( 2 + 、5 ) ，1 2 ，1 3 l ； 俐( k 4 ) ( 晶) ( 仇) p ( g ) ( r ) ，佗5 ，m 之6 j 似，( j ) p ( 姥( 仡一5 ，1 ，1 ) ) ，p ( 繇( 佗一5 ，l ，1 ) ) p ( d m ) ( n 6 ，仃l 4 ) ； 俐p ( 镌) p ( 坛) 风t 竹( 锯) ，m 5 i r 够彬( 移磊+ 1 ) p ( 谚毛) 卢( r ) p ( e t + 1 ) ，竹5 ，仇6 定义8 彬肘图8 ，选取e y ( g ) ，n c ( v ) = au ba n da nb = 毋。设日= ( g ，t ，a ，b ) 是如下定逻f p ) v ( h ) = y ( g ) 一u ) u u 1 ，秽2 ) ( 1 ，v 2 隹g ) ； 俐e ( 日) = 【e e ( h ) i e 不与t ，关联) uv l u l u a ) uv 2 u l u b ) 称h 是由g 分裂，粕得到的图记h = g i 。o 如果h 是由g 通过一系列点分裂得到的 图h 被称为图g 的点分裂图。 1 2 i 伴随多项式的代数性质 5 定义9 ( 3 1 d 对a ，bsy ( g ) ，者咖a ，矽b 均有础e ( g ) ，称a ，b 在g 中相 邻。 引理1 9 伊圳者h = ( g ，u ，a ，b ) ，贼l ( g ) = h i ( g 。) 当且仅当a z s b ；f f ：g 中相 邻。 引理1 1 0 伊1 1 ) 者g 是一棵树俾它经过一系列三角形二度点分裂后是一棵树，如 果讹u 刀( g ) ，但伽不属于g 的内部路，那么p ( 瓯甜) 3 岭、o 其中g 列表示在- g 的边叫增加一个新点得到的 图。 n 引理1 1 1 仍砂妣( z ) = a i j x j ，( i ；1 ，2 ，3 ，是首项系数为正的实系数多项 式，屈为 ( o ) = 1 ，2 ，3 ) 厅缀小实根，而且满足下面条件： 以，3 ( z ) = 1 2 ( z ) + ) ； ( 2 ) f 3 0 o k ( x 、) 最高项次数奇偶相异； 俐 ) 与- ，2 p ) 均有负实根且庞 p ( g ) 。 引理1 1 4 仍锄如果 历( z ) i 是一整系数多项式且鼽( z ) = z ( 鼽一l ( z ) + g n 一2 ( z ) ) ， 那么 f ，j ，匆n ( z ) = ( 尸k ) j 9 h k ( x ) + ( 尸k 一1 ) 9 n 一一1 ( z ) 砂危l ( ) 1 9 七( n + 1 ) + ( z ) 型且仅当h 1 ( 。) i 吼( 。) ，0 i n ，n 2 引理1 1 5 删渤，m22 ，l ( r ) i 九( 尸m ) 当且仅当佗+ z l m + l 。 弓理1 1 6 ( f 3 1 1 ) g 是一个图。 n ，) 如果g 妒，j 聚么b 3 ( g ) = h a ( d n + 1 ) 一2 ( n + 1 ) + t ，1 0 ts1 3 ； 例如果g ，那么b a ( g ) = b a ( d 仡) 一礼+ t ，4st 7 ； 6 3 ( g ) = 6 3 ( 风) 一礼+ 4 当且仅当g 1 器( n 一1 ，1 ) i7 , 25 ) u 器( 1 ，1 ) u 器( n - s ，l ，1 ) i 扎之7 ，； b a ( o ) = b a ( d n ) 一竹+ 5 当且仅当g 僻( r ，8 ) lr 4 ，s 2 u 繇( 1 ，n 一4 ) in2 6 ) u 器( r 1 ，t ) l7 ，t 2 ) u 嚣( 1 ，1 ，1 ) ； b a ( g ) = b 3 ( d n ) 一n + 6 当且仅当g 繇( r ，5 ) lr ，s 芝2 u 繇( n s ，t ) ，繇( 1 ，1 ，t ) l n5 ，t22 ) ； b a ( g ) = 6 ：| ( 巩) 一佗+ 7 当且仅当g 繇( 1 ，s ，t ) ls ，t 2 ) ； r 动如果g ( ，那么b a ( g ) = h a ( 玩+ 2 ) 一a ( n + 2 ) + t ，1 6s ts1 9 。 弓j 翌1 1 7 ( f s 6 j 若g 是一个n 阶的图且g 乏，燹l j 以，r 2 ( g ) = 3 当且仅当g 矗( 佗一1 ，1 ) i n 5 ) u 驻l ( 佗一5 ，1 ，1 ) i n 7 ) u 甓( 1 ，1 ) ； 6 第1 章引言 俐r 2 ( g ) = 4 当且仅当g 矗( r ，s ) l r 4 ，s 2 ) u 【醇( n 1 ，t ) l r ，t 2 ) u 繇( 1 ，礼一 4 ) i n26 ) u 镣； ( s ) r 2 ( a ) = 5 当且仅当g 繇( r 5 ，) ，舞( 1 ，1 ，t ) l r ，s ，t 2 u t 靠( r ，s ) l r ，s 之2 ) ； ( 4 ) r 2 ( a ) = 6 当且仅当g 簖( 1 ，s ，0 1 8 ，t 之2 ) 。 引理1 1 8 伊研j 者g 是一个t 阶的图且g 妒，则 以) 危( g ) = 7 当且仅当g 识l 佗5 ) u 织( r ，s ) l r 4 ，s 2 ) u 妒：一6 ，1 ) h 之 8 ) u 镌u 镌( 1 ，s ，t ) l s ，t 2 ) ； 俐r 2 ( a ) = 8 当且仅当g 镌i n 6 ，u 妒i ( 佗一3 ，t ) l n 7 u 妒：( r ，8 ) i t ，s 2 ) u 罐u 妒 u 诉( r ，5 ，t ) l r ，s ，t 2 ) ； 俐励( g ) = 9 当且仅当g 砩( 1 ，礼一6 ) i n 8 ) u 落( 1 ，1 ，1 ) u 鹕( r ，1 ，t ) l r ，t 2 ) ； 似，) r 2 ( g ) = 1 0 当且仅当g 妒昱( 他一7 ，1 ，t ) l n 9 ) 。 引理1 1 9 伊钏着g 是一介z 阶的图且g e ，则 以，r 2 ( g ) = 1 l 当且仅当g 矗l n 8 u 簖i ( r ，s ，t ) l r ，5 ，t 2 ，u 镌( r s ) l r ，s 2 ) ； 俐r 2 ( g ) = 1 2 当且仅当g 毋u 锯( 1 ，8 ，t ) l s ，t 2 u 岛( 1 ，n 一8 ) i n 1 0 ； 俐r 2 ( g ) = 1 3 当且仅当g 甓( 1 ，l ，佗一9 ) i n 1 1 ) ； 俐r 2 ( g ) = 1 4 当且仅当g 竺岛( 1 ，1 ，1 ) 。 引理1 2 0 伊2 2 剐r 2 ( f 6 ) = 5 ，r 2 ( r ) = 4 ( 佗7 ) ，r 2 ( d 4 ) = 0 ，r 2 ( d ) = l ( n 5 ) ；尼( t ( 1 ，1 ，1 ) ) = 一l ，r 2 ( t ( 1 ，l ，f 3 ) ) = 0 ，r 2 ( t ( 1 ，2 2 ，z 3 ) ) = 1 ，r 2 ( t ( z l ，1 2 ，z 3 ) ) 2 2 ；危( 尼) = 一l ，而( r ) = 一2 3 ) ，r 2 ( g ) = o ( 佗4 ) ，嘞( 甄) = 7 ，如( 巧) = 7 ；1 1 ，z 2 ，1 3 2 。 1 3 主要结果 定理1 2 当佗1 0 时，诱而工丽i 是伴随难一的。 定理1 3 当佗6 时，如( n 一2 ，3 ) 不是色唯一的。 定理1 4 如果g 繇( r ，1 ，( r ，t 1 ，札= r + t + 3 ) ，则郁( 繇( 佗一5 ，1 ，1 ) ) 卢( 繇( 他一4 ，1 ，2 ) ) p ( 繇( 竹一3 ，l ，3 ) ) p ( 簖( 2 ，1 ，n 一4 ) ) p ( 簖( 1 ，1 ，佗一5 ) ) 。 第二章 蝙( 仡二5 ，3 ) 的伴随等价与色等价图 2 1 前言 引理2 1 似g 驯p ，当佗26 肘，p n ( 篇) p 讯( 靠) 卢礼( 嚣1 ) 芦伽( 矗) ； 例勤之8 对，胁伽( 镌( r ，s ，t ) ) s 风 n 蝣( ns ) 风饥镌r ，s ) s 风讥镌风讥镌； 俐当n28 肘，m 饥( 蛾( r s ，t ) ) = 织一7 ，1 ，1 ) ，m 饥( 蝣( r ，5 ) ) = 镌( 1 ，扎一6 ) ； 俐当r21 ，t 之r 2 时，p ( 蝣( r ，s ，t ) ) p ( 妒i ( r s 一，l ，t + 1 ) ) ，p ( 诞( r + 1 ，s ，) ) p ( 妒：( r ，s ，t + 1 ) ) ；当s 7 22 时，p ( 织( r ，5 ) ) 卢( 妒：( r 一1 ，s + 1 ) ) ； ，俐当佗8 肘，m 凹( 簖( r ，5 ，t ) ) = 甓( 佗一5 ，1 ，1 ) ，m 凹( 矗( r ，1 ) ) = 姥 一1 ，1 ) 。 咖2 2 艄喇对，a ( h i ( 蜘刮) ) ： 车，冀冀 。、。，m ，l 罟，f l , 9 y l t 鳜一； 俐当n 9 时，口( 惦一5 ，3 ) ) 2 车，礼为奇数 俐兰i 仡1 1 对，危( 矽i ( n 一5 ，3 ) ) = z ( 矽i 一1 ( 住一6 ，3 ) ) + z ( 妒i 一2 ( n 一7 ，3 ) ) 。 证明? ( 1 ) 选圈上一边e = u 口e ( g ) 且两点满足d ( u ) = 2 , d ( v ) = 3 。由引理1 1 ， 则可有尼( 织( 佗一5 ，3 ) ) = 危( d n ) + x h ( p n 一7 ) ( 现) 。再由引理1 3 ，可得o ( h l ( d ) ) = 【! 气p j 且a ( 1 ( r 一7 ) ) a ( 危1 ( d 5 ) ) = 【! 宁j + 3 ， 如果扎为偶数，则有l 学i = 警 孚- i - 3 = 孚； 如果佗为奇数，有i 学i = 学 字4 - 3 = 学。因而结论成立。 ( 2 ) 由( 1 ) 的证明可知( 2 ) 成立。 ( 3 ) 选圈上一边e = u u e ( g ) 且两点满足d ( u ) = 2 ，d ( v ) = 3 。由引理1 1 和1 2 可有 h ( 妒i ( 仡一5 ，3 ) ) = u ( d n ) + x h ( p n 一7 ) h ( d 5 ) ：= x ( h ( d 。一1 ) 4 - 危( d n 一2 ) + z ( 危( 。r 一8 ) + h ( d n 一9 ) 危( d 5 ) ) = z ( 危( d n 一1 ) + x h ( r 一8 ) 危( d 5 ) ) + z ( 九( d n 一2 + x h ( d n 一9 ) 危( d 5 ) ) = z ( 妒：一l ( n 一6 ，3 ) ) + z ( 妒i 一2 ( 佗一7 ，3 ) ) 因此结论成立。 r j i r 2 3 当n29 时，p ( 妒熹( n 一5 ，3 ) ) 口( 矽i + l ( n 一4 ，3 ) ) 。 7 口 8 第2 章碉丽i 丽的伴随等价与色等价图 证明：( 1 ) 当他= 9 b , j - ，直接计算有：p ( 孵( 4 ，3 ) ) = 一4 4 7 2 8 3 - 4 5 3 9 9 9 = p ( 妒扎( 5 ，3 ) ) 。 结论成立。 ( 2 ) 若佗= k ，( 惫1 0 ) 时，p ( 镤( 丘一5 ，3 ) ) p ( 妒玉1 ( 忌一4 ，3 ) ) 成立，则当n = 尼+ 1 有， h ( 识+ l ( 七一4 ，3 ) ) = z ( 砂2 ( 一5 ，3 ) ) + x h ( d l ( 七一6 ，3 ) ) 令 ( z ) = x h ( 喉3 1 ( 七一6 ，3 ) ) ，f 2 ( x ) = z h ( 妒2 ( 岛一5 ，3 ) ) ，h ( x ) = 危( 砂2 + 1 ( 凫一4 ，3 ) ) 。 不难发现上式满足引理1 1 1 1 簦j 条件，因此可得p ( 蝶( 七一5 ，3 ) ) p ( 妒玉1 ( 七一4 ，3 ) ) ， 根据归纳假设，可知此引理成立。 口 弓1 j $ 2 4 似钏卢( 以) p ( 嘏一4 ，2 ) ) 。特别地，p ( 蜡) p ( 讥) = 卢( 锻( 4 ，2 ) ) p ( 讲) p ( 蛾1 ) p ( 螂1 ) = p ( 稍( 5 ，2 ) ) p ( 妒 o ( 6 ，2 ) ) 。 弓i 理2 5 当他1 l l r f ，p ( 惦( n 一5 ，3 ) ) p ( 妒：) 。特j g 矿地，( 孵( 4 ，3 ) ) = p ( 妒 ) p ( 妒孔( 5 ，3 ) ) p ( 妒 1 ( 6 ，3 ) = p ( 妒( 4 ，2 ) ) = p ( 蛾1 ) a 证明? ( 1 ) 当死= 1 1 时， m ( 2 1 ) 和( 2 2 ) 可有 危( 镌( 佗一5 ，3 ) ) = h ( d n ) + x h ( p n t ) h ( d s ) 危( 以) = h ( d n ) + x h ( p 一2 ) ( 2 1 ) ( 2 2 ) 九( 妒i ( 佗一5 ，3 ) ) 一九( 妒矗) = x h ( r 一7 ) h ( d 5 ) 一z h ( p 2 ) = o h ( f k z ) h ( d s ) 一x h ( p , 一t ) h ( p 5 ) 一x 2 h ( p 4 ) h ( p n 一8 ) = z ( z 4 + 2 x 3 + x 2 ) 危( j 气一7 ) 一t , 2 h ( p a ) h ( p n 一8 ) = ( z 2 + 2 x + 1 ) h ( p n 一7 ) 一z 3 ( z 3 + 3 x 2 + x ) h ( p n 一8 ) = x 3 【( z 3 + 2 x 2 + z ) ( r 一8 ) + ( z 3 + 2 x 2 + 功 ( r 一9 ) 一( z 3 + 3 x 2 + z ) 危( r 一8 ) 】 = z 3 ( 矿+ 2 x 2 + z ) 危( 只。一9 ) 一z 2 愚( 岛一8 ) 】 = x 3 【( 童3 + 2 x 2 + z ) 一x 3 ( 只l 一9 ) 一z 3 h ( p n l o ) 】 = x 3 【( 2 2 2 + z ) ( 。r 一9 ) 一z 3 ( r l o ) 】 = x 3 【( 2 2 3 + 护) 危( j 一1 0 ) + ( 2 x 3 + x 2 ) 危( 只。一1 1 ) 一z 3 危( f 一1 0 ) 】 = ( z 6 + 墨5 ) ( r 一1 0 ) + ( 2 x 6 + x 5 ) ( 只，一1 1 ) 令，( z ) = ( z 6 + z 5 ) ( r 一1 0 ) + ( 2 2 6 + z 5 ) h ( p n 一1 1 ) 。当 r t i i 时，p ( ( z 6 + 护) ( j 一1 0 ) ) = p ( 岛) 且p ( 2 2 6 + x 5 ) 危( r 一1 1 ) ) = p ( r 1 1 ) ；又恳为r 1 0 和r 一1 1 的真子图及由 弓l 理1 1 1 和1 1 3 ，贝0 p ( p k 一1 1 ) p ( 尼) 。 又因为九( 惦机一5 ，3 ) ) = 危( 以) + ，( z ) 且r 一1 1 为妒竞( 佗一5 ，3 ) 和识的真子图 且0 1 ( h ( 妒：) ) = 佗与0 1 ( ，( z ) ) = 仡一4 的奇偶性相同及z j l 理1 1 2 和1 1 3 ，所以p ( 以) p ( 惦( n 一5 ，3 ) ) p ( j 一1 1 ) 。 ( 2 ) 运用m a t h e m a t i c a 软件直接计算：可有( 礁) = p ( 蛾( 4 ，3 ) ) = - 4 4 9 0 8 6 ， z ( 妒f o ( 5 ，3 ) ) = - 4 5 3 9 9 9 ，卢( 妒 1 ( 6 ，3 ) ) = p ( 媚( 4 ，2 ) ) = ( 以) = - 4 5 6 1 5 5 。从而 结论正确。 口 2 2 主要结果及证明9 引理2 6 当佗1 2 ，m 1 0 肘，p ( 碟( 礼一5 ，3 ) p ( 镌( m 一6 ，1 ) 。 稠伤2 地，p ( 妒 1 ( 6 ，3 ) ) = p ( 锻( 2 ，1 ) ) p ( 妒扎( 5 ，3 ) ) p ( 镏( 4 ，3 ) ) = p ( 谐( 3 ，1 ) ) 。 证h ：运用 纯t 危e m a 扰软件直接计算：则p ( 妒 1 ( 6 ，3 ) = p ( 镌( 2 ，1 ) = 一4 5 6 1 5 5 ， p ( 镑( 4 ，3 ) = p ( 谐( 3 ，1 ) = - 4 4 9 0 8 6 ，由引理2 3 与1 1 0 ；容易得到卢( 镌一5 ，3 ) ) 卢( 妒 1 ( 6 ，3 ) ) = p ( 妒( 2 ，1 ) ) 卢( 妒知( 5 ，3 ) ) ( 荫( 4 ，3 ) ) = p ( 诺( 3 ，1 ) ) 卢( 妒袅( m 一 6 ，1 ) ) ，因而结论成立。 引理2 7 当佗9 ，m 6 对，卢( 镌( n 一5 ，3 ) ) p ( 晶) 。 口 证明：运用 缸沈e m 口巧软件直接计算：p ( 媚( 4 ，3 ) ) = 一4 4 9 0 8 6 ，p ( 岛) = 一4 3 9 0 2 6 ， 又由引理i 8 ( 5 ) ) a 2 3 ，因此结论成立。 口 弓l 理2 8 当n 9 时，p ( 妒i ( n 一5 ，3 ) ) p ( 镌( 他一5 ，3 ) ) 。 口 引理2 9 似j 当扎9 ，m 1 0 0 1 ，p ( 嫔( n 一5 ，3 ) ) p ( 娘( 1 ，2 ，m 一8 ) ) 。特别 地，( 妒 1 ( 6 ，3 ) ) = p ( 妒 1 ( 1 ，2 ，2 ) ) 卢( 妒扎( 5 ，3 ) ) p ( 媚( 4 ，3 ) ) p ( 妒i ( n 一 5 ，3 ) ) 。 证明? ( 1 ) 当i t 9 ，m21 0 时，用m a t h e m a t t c a 软件直接计算：可得p ( 硼( 4 ，3 ) ) = p ( 媚4 ( 3 ，1 ) ) = - 4 4 9 0 8 6 ，( 砂扎( 1 ，2 ，2 ) ) = p ( 砂 l ( 6 ，3 ) ) = - 4 。5 6 1 5 5 ，p ( 砂扎( 5 ，3 ) ) = 一4 3 9 9 9 ，p ( 妒 l ( 1 ，2 ，3 ) = - 4 5 0 1