（应用数学专业论文）几类图的（排斥排斥整下整）和数.pdf

独创声明 y 1 0 1 2 4 8 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：南秀壹 导师签字： 学位论文版权使用授权书 南黝狻一 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权越可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：谭携莲 导师签字 高蚓钆 签字日期：2 0 0 年月 日签字日期：2 0 0 年f 月纠伯 山东师范人学硕士学位论文 几类图的( 排斥，排斥整，下整) 和数 高秀莲 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 本文仅考虑有限无向简单图，所用图论基本术语与符号遵循文献” 1 9 9 0 年h a r a r y 2 1 提出和图的概念1 9 9 4 年h a r a r y _ 3 1 提出整和图的概念令n ( z ) 表示正整数( 整数) 集，n ( z ) 的非空有限子集s 的和( 整和) 图g 十( s ) 是图( s ，e ) ，其中u v e e 当且仅当u + v e s 一个图g 称为和( 整和) 图，若它同构于某个s c n ( z ) 的和( 整 和) 图此时我们说s 给出了g 的一个和( 整和) 标号，并且将顶点与其标号不加区 分g 的和数( 整和数) o - ( g ) ( f ( g ) ) 是使得g un k l 是和图( 整和图) 的非负整数 n 的最小值 2 0 0 3 年m i l l e r 4 1 等人提出排斥图的概念图g u n k l 的( 整) 和标号s 称为排斥 的( e x c l u s i v e ) ，若对每条边u v e e ( g ) ，u + v s v ( g ) 图g 的排斥和( 整和) 数占( g ) ( f ( g ) ) 是使得g u n k l 有排斥和( 整和) 标号的非负整数n 的最小值 2 0 0 4 年李敏5 1 提出下整和图的概念令q + 表示正有理数集o + 的非空有限 子集s 的下整和图g 十( s ) 是图( s ，e ) ，其中u v ee 当且仅当b u + v j e s 一个 图g 称为下整和图，若它同构于某个s co + 的下整和图我们说s 给出g 的 一个下整和标号，并且顶点与标号不加区分下整和数叮( g ) 是使得g u n k l 是下 整和图的非负整数u 的最小值 图g u n k l 的下整和标号s 称为排斥的( e x c l u s i v e ) ，若对每条边u v ee ( g ) 当且仅当b u + v j e s v ( g ) 图g 的排斥下整和数占7 ( g ) 是使得g un k i 有 排斥下整和标号的非负整数n 的最小值 从实用的观点来看，各种和图标号都可被计算机用作图的压缩表示当利用它 们来工作时，不仅可以节省内存，还可以加快某些图算法的运算速度 在本文的第一章中，我们主要介绍了一些文章中所涉及的概念，术语，符号；第 二章介绍了棱柱e i l ( n 3 ) 、残棱柱e ：( i l 3 ) 、残皇冠c ：。k l ( n 3 ) 、梯子 山东帅范大学硕十学位论文 l 。( n 2 ) 、梯子细分图l ：( n 2 ) 的概念，并给出了1 邑们的排斥( 整，下整) 和数：第三章给出了三毛虫树，星毛虫树，广义双星，广义毛虫的概念，并证明 了这几类特殊的树是整和图 我们主要得到如下结果 定理2 1设n 为大于等于3 的自然数，则s ( e ) 2 5 定理2 2设n 为大于等于3 的自然数，则f7 ( e ：) = 4 定理2 3设n 为大于等于3 的自然数，则s ( qo k l ) 2 3 定理2 4l n ( n 2 ) 是下整和图 定理2 5设n 为大于1 的自然数，则占( 匕) = 1 定理2 6设n 为大于1 的自然数，则s ( ) 2 3 定理2 7设n 为大于1 的自然数，则7 ( t ) = 2 定理3 1三毛虫树是整和图 定理3 2偶星毛虫树是整和图 定理3 3广义双星是整和图 定理3 4广义毛虫是整和图 关键词：( 排斥，下整，整) 和图：( 排斥，下整，整) 和数：( 排斥，下整， 整) 和标号；( 残) 棱柱；残皇冠；梯子；整和树 分类号： 0 1 5 7 5 山东师范大学硕士学位论文 t h e ( e x c l u s i v e ，e x c l u s i v ei n t e g r a l ，l o w e ri n t e g r a l ) s u m n u m b e r so fs e v e r a lk i n d so fg r a p h x i u l i a ng a o s h a n d o n gn o r m a lu n i v e r s i t y , j i n a n ，s h a n d o n g ，2 5 0 0 1 4 p e o p l e sr e p u b l i co f c h i n a a b s t r a c t a l lg r a p hc o n s i d e r e di nt h i sp a p e ra r ef i n i t e ，s i m p l ea n du n d i r e c t e d w ef o l l o wi n g e n e r a lt h eg r a p h - t h e o r e t i cn o t a t i o na n dt e r m i n o l o g yo f 1 】 h a r a r y t 2 1p r e s e n t e dt h ec o n c e p to fs u mg r a p hi n1 9 9 0 h a r a 3 1p r e s e n t e dt h e c o n c e p to fi n t e g r a ls u n lg r a p hi n1 9 9 4 l e tn ( z ) d e n o t et h es e to fa l lp o s i t i v e i n t e g e r s ( i n t e g e r s ) t h e ( i n t e g r a l ) s u l - ng r a p hg 十( s ) o fan o n e m p t yf i n i t es u b s e t s c n ( z ) i st h eg r a p h ( s ，e ) w i t h u vei f a n do n l yi fu + v e s ag r a p hg i ss a i dt ob ea l l ( i n t e g r a l ) s u n lg r a p hi fi ti si s o m o r p h i ct ot h e ( i n t e g r a l ) s u l l lg r a p ho f s o m escn ( z ) w es a i dt h a tsi so n eo ft h e ( i n t e g r a l ) s u ml a b e l i n g ，a n dw e c o n s i d e rt h ev e r t i c e sa n dl a b e l i n g sa st h es a n l e t h e ( i n t e g r a l ) s u mn u m b e r 盯( g ) ( f ( g ) ) i st h es m a l l e s tn u m b e ro fi s o l a t e dv e r t i c e sw h i c hw h e na d d e dt o g r e s u l t e di na n ( i n t e g r a l ) s u n lg r a p h m i l l e d ”p r e s e n t e dt h ec o n c e p to fe x c l u s i v eg r a p hi n2 0 0 3 as u l t il a b e l i n gs i sc a l l e da ne x c l u s i v es u l nl a b e l i n g ，i fu + ves v ( g ) f o ra n ye d g eh vee ( g ) t h e e x c l u s i v es u l n ( i n t e g r a ls l l i t i ) n u m b e r 占( g ) ( f ( g ) ) o fgi st h el e a s tn u m b e r w h i c hw h e na d d e dt ogr e s u l t e di ni sa ne x c l u s i v es u n 3 ( i n t e g r a ls u m ) g r a p h i n2 0 0 4 ，l im i n 【”i n t r o d u c e dt h ec o n c e p to fl o w e ri n t e g r a ls h i l lg r a p h l e t 叮d e n o t et h es e to fa l lt h ep o s i t i v er a t i o n a ln u m b e r t h el o w e ri n t e g r a ls u mg r a p hg + ( s ) o f a n o n e m p t y f i n i t es u b s e ts cq + i s t h eg r a p h ( s ，e ) w i t h u v ei f a n d o n l yi fl u + v j e s a g r a p h gi ss a i dt ob ea nl o w e ri n t e g r a ls i n t lg r a p hi f i ti s i s o m o r p h i ct ot h el o w e ri n t e g r a ls r i t ig r a p ho f s o m escq + t h el o w e ri n t e g r a l 4 山东师范大学硕十学位论文 s u mn u m b e r 盯( g ) i st h es m a l l e s tn u m b e ro f i s o l a t e dv e r t i c e sw h i c hw h e na d d e dt o gr e s u l t e di nal o w e ri n t e g r a ls u mg r a p h al o w e ri n t e g r a ls u ml a b e l i n gsi sc a l l e da ne x c l u s i v el o w e ri n t e g r a ls u m l a b e l i n g ，i fl u + v i es v ( g ) f o r a n ye d g eu v ee ( g ) t h ee x c l u s i v el o w e ri n t e g r a l s u mn u m b e r s ( g ) o f gi st h el e a s tn u m b e rw h i c hw h e na d d e dt ogr e s u l t e d i ni sa ne x c l u s i v el o w e ri n t e g r a ls u mg r a p h f r o map r a c t i c a lp o i n to fv i e w , s u mg r a p hl a b e l l i n gc a nb e u s e da sa c o m p r e s s e dr e p r e s e n t a t i o no f a g r a p hb yc o m p u t e r d a t ac o m p r e s s i o ni si m p o r t a n tn o t o n l yf o rs a v i n gm e m o r ys p a c eb u ta l s of o rs p e e d i n gu ps o m eg r a p ha l g o r i t h m sw h e n a d a p t e dt ow o r k w i t ht h ec o m p r e s s e dr e p r e s e n t a t i o no f t h ei n p u tg r a p h t h ef i r s tc h a p t e ro ft h i st h e s i sg i v e sab r i e fi n t r o d u c t i o na b o u tt h eb a s i c c o n c e p t s ，t e r m i n o l o g i e sa n ds y m b o l sw h i c ha r eu s e di n t h i sp a p e r ；i nt h es e c o n d c h a p t e rw ei n t r o d u c es o m ec o n c e p t so fp r i s m ，i n c o m p l e t ep r i s m ，i n c o m p l e t ec r o w n ， l a d d e ra n ds u b d i v i s i o ng r a p ho fl a d d e ra n dg i v et h ee x c l u s i v e ( i n t e g r a l ，l o w e ri n t e g r a l ) s u m n u m b e r so f t h es e v e r a lk i n d so fg r a p h i nt h et h i r dc h a p t e rw eg i v es o m ec o n c e p t so f3 一c a t e r p i l l a rt r e e ，s t a r c a t e r p i l l a rt r e e ，g e n e r a l i z e dd o u b l es t a ra n dg e n e r a l i z e d c a t e r p i l l a r w ep r o v et h es e v e r a lk i n d so f t r e e sa r ei n t e g r a ls u mg r a p h i nt h i st h e s i sw eo 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 m2 1f o r n 3 ，( e ) 2 5 t h e o r e m2 2f o rn 3 ，f7 ( e ：) = 4 t h e o r e m 2 3f o r n 3 ，s ( eo k l ) 2 3 t h e o r e m2 4f o rn 2 ， k a r el o w e ri n t e g r a ls u m g r a p h s t h e o r e m2 5f o r n l ，s ( l ) 2 1 t h e o r e m2 6f o r n l ，s ( e ) 2 3 t h e o r e m2 7f o r n l ，占7 ( 三：) = 2 t h e o r e m3 1 3 - - c a t e r p i l l a rt r e e sa r ei n t e g r a l s h i l l g r a p h s 5 6 东师范人学硕士学位论文 t h e o r e m3 2e v e ns t a r - c a t e r p i l l a rt r e e sa r ei n t e g r a ls u mg r a p h s t h e o r e m3 3g e n e r a l i z e dd o u b l es t a r sa r ei n t e g r a ls h i l lg r a p h s t h e o r e m3 4g e n e r a l i z e dc a t e r p i l l a r sa r ei n t e g r a ls u mg r a p h s k e yw o r d s ：( e x c l u s i v e ，l o w e ri n t e g r a l ，i n t e g r a l ) s u mg r a p h ；( e x c l u s i v e ， l o w e ri n t e g r a l ，i n t e g r a l ) s u mn u m b e r ；( e x c l u s i v e ，l o w e ri n t e g r a l ，i n t e g r a l ) s u m l a b e l i n g ；( i n c o m p l e t e ) p r i s m ，i n c o m p l e t ec r o w n ，l a d d e r , i n t e g r a ls u mt r e e c l a s s i f i c a t i o n ：0 】5 7 5 山东师范大学硕士学位论文 第一章引言 1 9 9 0 年h a r a r y 2 1 提出和图的概念1 9 9 4 年h a r a 拶3 1 提出整和图的概念令n ( z ) 表示f 整数( 整数) 集，n ( z ) 的非空有限子集s 的和( 整和) 图g + ( s ) 是e f l ( s ，e ) ，其中u v e 当且仅当u + ve s 一个图g 称为和( 整和) 图，着它同构于某个s c n ( z ) 的和( 整 和) 图此时我们说s 给出了g 的一个和( 整和) 标号，并且将顶点与其标号不加区 分显然若图g 是和图则必不连通( k l 除外) ，但总可以给g 加上有限个孤立点 使之成为和图。g 的和数( 整和数) 盯( g ) ( f ( g ) ) 是使得g un k l 是和图( 整和 图) 的非负整数n 的最小值 1 9 9 0 年b o l a n d 6 1 等人提出模和图的概念模和图是取s cz m 0 且所有算术 运算均取模m ( l s i + i ) 的和图由此，2 0 0 2 年s u t t o n 7 1 等人提出了模和数的概念 一个图g 的模和数p ( g ) 是使得g up k l 是模和图的非负整数p 的最小值 2 0 0 3 年m i l l e r 4 1 等人提出排斥图的概念图g u n k l 的( 整) 和标号s 称为排斥 的( e x c l u s i v e ) ，若对每条边u vee i ：g ) ，u + ves v ( g ) 图g 的排斥( 整) 和数6 ( g ) ( f7 ( g ) ) 是使得g u n k l 有排斥( 整) 和标号的非负整数n 的最小值一个连通 图的最大度彳是其排斥和数的下界，能达到此下界的图称之为排斥4 一最优的 显然对任意的图g 有f ( g ) 盯( g ) c ( g ) ；q ( g ) f7 ( g ) 6 ( g ) 显然一个图如果是排斥彳一最优的，则f7 ( g ) = e ( g ) 2 0 0 3 年m i l l e r 4 1 等人提出如下公开问题： 问题：对各类图确定其排斥和数 2 0 0 4 年，李敏5 1 提出下整和图的概念令q + 表示正有理数集o + 的非空有 限子集s 的下整和图g + ( s ) 是图( s ，e ) ，其中u ve 当且仅当l u + v j e s 一 个图g 称为下整和图，若它同构于某个s cq + 的下整和图我们说s 给出g 的一个下整和标号，并且顶点与标号不加区分下整和数盯( g ) 是使得g u n k l 是 下整和图的非负整数n 的最小值 图g un k l的下整和标号s 称为排斥的( e x c l u s i v e ) ，若对每条边u v e ( g ) ，b + v j s v ( g ) 图g 的排斥下整和数6 ( g ) 是使得g un k l 有排斥 山东师范人学硕士学位论文 下整和标号的非负整数n 的最小值 从实用的角度来看，各种和图标号都可被计算机用作图的压缩表示当利用 它们来工作时，不仅可以节省内存，还可以加快某些图算法的运算速度 目前对和图的研究主要集中在两个方面：一方面研究图的( 模整，模，整，排斥) 和数与其它图参数，图结构的联系；另一方面确定一些特殊图类的和数，整和数，模 和数模整和数及排斥和数 经过许多人的研究，目前已确定一些常见图类，如完全图k ，完全二分图k 。， 圈c 。，n + 1 个顶点的轮w n ，n + 1 个顶点的扇f n ，酒会图h 2 ，。等图的( 模，整，模 整，排斥) 和数这些结果可参见8 _ “与本文密切相关的结果如下： 定理a 1 除c 。ok 】外所有皇冠图都是整和图 定理b 。“c 。o k ，和c ：o k l 和数都为1 定理c ”下整和图g 若包含c 6 作为其导出子图，则工作点数大于1 定理d “”任意一棵树( k 1 除外) 的和数都是1 定理e ”1 阶数不小于3 的树是模和图 定理f ”1 对任意正整数n ，路p n 是整和图 定理g “3 1 存在无数个不是毛虫的整和树 定理h0 7 3 叉点距离至少为4 的树是整和图 定理i 。7 3 广义星是整和图 定理j 。1 毛虫是整和图 定理k “3 灌木都是整和图 定理l 1 叉点距离至少为2 的树是整和图 定理m 啡1 完全二叉树是整和图 文中所涉及的符号为：a 斗术b 表示整数a 的个位数字为b ，a 一木b 表示集合 a 中的元素的个位数字为b 山东师范大学硕上学位论文 第二章几类图的排斥( 整) 和数与( 排斥) 下整和数 本章的各节中我们首先给出了几类图的定义，然后通过给出这几类图的f 排 斥，排斥整，下整) 和标号，分别验证了其( 排斥，排斥整，下整) 和数的上界与其 下界相等，从而确定了其( 排斥，排斥整，下整) 和数 2 1( 残) 棱柱的排斥( 整) 和数 定义2 1c k ：称为棱柱，记为e 。；其中c 。为棱柱的上下底面将棱柱 上下底面的边c 。进行一次剖分，形成的图称为残棱柱，记为e ： 图2 1 棱柱e 。的平面图 图2 2 残棱柱e ：的平面图 山东师范大学碗士学位论文 王海英口4 ，给出了棱柱e ( n 3 ) 的和数的上界为 ；：舅鬈篓、整和数的上界 为 ：曼罢萋回钰【3 5 1 给出了残棱柱e ( n 3 ) 整和数的上界为5 这里我们将分 别给出棱柱的排斥和数是5 、残棱柱的排斥整和数是4 ，从而改进了她们的结果 定理2 1 设r l 为大于等于3 的自然数，则占( e r i ) = 5 证明：( 一) 先证( b ) 5 不妨设a l - w n a x v ( f 。) ，a k - - m i nv ( e 。) 分以下两种情形： 1 ) 若a 1 ，a k 不相邻：考虑与a 1 ，a k 邻接的边和a 1 + a 2 ，a l + a n ，a 1 + b t ，a k + a k + 1 ， a k + a k 1 a k + b k ，且m a x a k + a k + 1 ，a l ( + a k - 1 ，a k + b k c 5 c 2 c 4 2 ) 验证任意边和属于s v ( e 2 。) a i + a f + 1 = a ；+ 6 0 l = ( 2 n i + 1 ) x 1 0 + 1 + o + 1 一1 ) 1 0 + 3 = ( 2 n + 1 ) x 1 0 + 4 = c l i = 1 , 3 ，2 n l d f + d l 十l = a t + 彬= ( 2 n i l + 1 ) x l o + l + ( i 一1 ) x l o + 3 = ( 2 ”一1 ) x 1 0 + 4 = c 2f = 2 , 4 ，2 n 一2 a 1 + 口2 。= a ：+ 6 。= ( 2 n l + 1 ) 1 0 + 1 + ( 2 刀- 1 ) x 1 0 + 3 = ( 4 n 一1 ) x 1 0 + 4 = c 3 岛+ 岛“= 口二l + 6 f = ( 2 n i l + 1 ) x 1 0 + l + ( i 一1 ) x 1 0 + 3 = ( 2 ”一1 ) x 1 0 + 4 = c 2 i = 1 , 3 ，一，2 n l b i + 6 f + 1 = n ：+ 6 0 1 = ( 2 n i + 1 ) 1 0 + 1 + 0 + 1 - 1 ) x l o + 3 = ( 2 n + 1 ) 1 0 + 4 = c 1 i = 2 , 4 ，一，2 n 一2 b l + b 2 。= 6 f + d 幺= 1 4 = c 4 口i + 阮2 a ：+ 噬2 ( 2 刀一k + 1 ) x 1 0 + l + ( 七一1 ) x l o + 3 = 2 n x l 0 + 4 = c 5 k = 1 , 2 ，3 , - - - , 2 n 3 ) 验证任意不邻接顶点标号之和不属于s ( 1 ) 考虑a 中元素：不妨设a i ，a j 不相邻( i j ) ，则 若i j 同奇偶： 由于a j + a i + 2 或a j + a i 一* 6 ， 二a i + a s 若巧奇偶互异： a i + a j 一+ 4 只须证a i + a jc ( j i + 1 ) i 为偶，j 为奇时： 巩+ a j - b i + a j _ ( i 1 ) x1 0 + 3 + ( 2 n - j + 1 ) 1 0 + 1 = ( 2 n + i - j ) x1 0 + 4 由于 3 j i ( 2 n 一1 ) 一2 ， 3 - 2 n 巧一3 即c 4 。1 4 3 4 a i + a j = ( 2 n + i - j ) 1 0 + 4 ( 2 n - 3 ) x 1 0 + 4 ( 2 n 一1 ) x 1 0 + 4 = c 2 故a + a j 匹c i 为奇，j 为偶时： a i + a j = a j + b i _ ( 2 n i + 1 ) x1 0 + 1 + 0 1 ) x1 0 + 3 = ( 2 n + j - i 、1 0 + 4 由于3 j i 2 n 一1 ， 山东师范大学硕上学位论文 即c l ( 2 n + 3 ) 1 0 + 4 一 a i + a j = ( 2 n + j i ) 1 0 + 4 i 时： 2 j i 2 n l l = 2 n 一2 ， c l ( 2 n + 2 ) 1 0 + 4 a i + b j = ( 2 n + j i ) x1 0 + 4 ( 4 n 一2 ) x1 0 + 4 c 3 a , + b j 芒s 当j i 时：2 - 2 n j i 一2 ， c 4 2 4 、 a ，十a 。= ( 2 n + j i ) x1 0 + 4 ( 2 n 一2 ) 1 0 + 4 i 时： 2 j i 一 2 n 一2 ， 2 - 2 n i - j 一2 ， c 4 2 4 a + b 。= ( 2 n + i j ) x1 0 + 4 ( 2 n 一2 ) x1 0 + 4 c 2 当j i 时：2 i j 2 n 一2 ， c ， ( 2 n + 2 ) x1 0 + 4 一 c 5 c 4 c 2 且c 2 a j ，c 2 b j ，c 2 2 a l b 1 从而a u b u c 中元素互异 2 ) 验证任意边和属于s v ( e 。) = c a f + 以l + l = + 彭“= ( 2 以一i + 2 ) 1 0 + 1 + 0 + 1 ) 1 0 + 3 = ( 2 甩+ 3 ) 1 0 + 4 = c 1 i = 3 ，5 ，2 n 一1 a 。+ 以i + 1 = a i + l p + 群= ( 2 n f 一1 + 2 ) x 1 0 + l + i x l 0 + 3 = ( 2 n + 1 ) 1 0 + 4 = c 2 f = 2 ，4 ，2 n a l + 拉2 = a 1 + 噬= 2 n 1 0 + 7 + 2 x 1 0 + 3 = ( 2 n + 3 ) x 1 0 = c 3 a l + 口2 肼l = a 1 + ；肘l = 2 n 1 0 + 7 + 2 n 一( 2 n + 1 ) + 2 1 0 + 1 = ( 2 n + 1 ) 1 0 + 8 = c 4 b i + 6 l + l = 口0 + 掣= ( 2 n f 一1 + 2 ) 1 0 + 1 + i x l 0 + 3 ：( 2 n + 1 ) x 1 0 + 4 = c 2 f = 3 , 5 ，2 n 一1 b f + b i “= 以；+ 6 三+ 】= ( 2 n i + 2 ) 1 0 + 1 + ( i + 1 ) 1 0 + 3 = ( 2 n + 3 ) 1 0 + 4 = c l i = 2 , 4 ，2 甩 1 3 h 东师范人学硕上学位论义 6 1 + b 2 。= 6 j + 以；= 1 7 + ( 2 n 一2 + 2 ) 1 0 + l = ( 2 n + 1 ) 1 0 + 8 = c 4 b l + b 2 = 岛+ 噬= 1 7 + ( 2 n + 1 ) x 1 0 + 3 = c 3 日t + = a ：+ “= ( 2 n k + 2 ) x 1 0 + 1 + k x l o + 3 = ( 2 n + 2 ) 1 0 + 4 = c 5k = 1 , 2 ，3 ，2 n + a 1 + 6 l = 2 n x l 0 + 7 + 1 7 = ( 2 n + 2 ) 1 0 + 4 = c e 3 ) 验证任意不相邻接的顶点标号之和不属于s 3 1 ) 考虑a 中元素：不妨设a ，a ，不相邻( i c 3 故a j + a ，gs ( 2 ) 然后考虑一般情况a i ，j 同奇： a i + a 。= a i + a j 一+ 2 ， 故a i + a ，萑s i ，j 同偶： a t + a j = b l + b j 一+ 6 ， 故a 。+ a ，g s i 奇，j 偶( j i + 1 ) ： a i + a j 2 a i + b j 2 ( 2 n i + 2 ) x1 0 + 1 + j 1 0 + 3 = ( 2 n + 2 + j i ) 1 0 + 4 ( 2 n + 3 ) 1 0 + 4 = c 。 故a i + a 萑s i 偶，j 奇( j i + 1 ) ： a i + a 一= b i + a j 爿1 0 + 3 + ( 2 n i + 2 ) 1 0 + l = ( 2 n + 2 + i _ j ) 1 0 + 4 弋 ( 2 n 一1 ) 1 0 + 4 2 ) i ，j 同偶：a j + b 。= b i + a j 仨s i 奇，j 偶： a i + b ，= a i + a j 一+ 2 ； i 偶，j 奇a j + b j = b j + b i 一+ 6 ， 故a 。+ b 。s 3 4 ) 显然c 间无连边，c 与a u b 无边相连 综上所述，此标号的确为e 2 n t lu5 k ，的一个排斥和标号， 即占( e 2 。十1 ) 5 由( 一) 、( - 3 知s ( e ) = 5 推论2 1f ( e ) a ( e 。) s ( e ) = 5 定理2 2 当n 3 时，残棱柱的排斥整和数等于4 即f7 ( e ：) = 4 证明：( 一) 先证f7 陋：) 4 设a l = m a xv ( 彰) ，a k - = 【n i n v ( e ) ，分以下三种情况： 1 ) a 1 ，a k 均为2 度顶点：则a 1 ，a k 不相邻，考虑与a 1 ，a k 邻接的边和a l + a 2 。 a l + a 2a k + a k - la k + a k 1均为缘边，且m a x a k + a k + 1 ，a k + a k 1 ) m i n a l + a 2 。， a l + a 2 ，互不相等 2 ) a 1 ，a t 均为3 度顶点： 山东师范大学硕士学位论文 ( 1 ) 若a 1 ，a k 不相邻，考虑与a 1 ，a k 邻接的边和a l + a 2a l + a 2 。a 1 + b 1 ， a k + a k + 1 ，a k + a k i ，a k + b k ，且 m a x a k + a k + 1 ，a k + a k i ，a k + b k ) r a i n a l + a 2 n ，a l + a 2 ，a t + b t ， 互不相等 ( 2 ) 若a 1 ，a k 相邻，不妨设a k - - b 1 考虑与a l , a k 邻接的边和a 1 + a 2 ，a l + a 2 。，a l + b 1 b l + b 2 ，b l + b 2 t l 且m a x b l + b b 1 + b 2 ) m i n a l + a 2 n ，a l + a 2 ，a l + b l ，互不相等 3 ) a l ，a k 一个为3 度顶点，一个为2 度顶点： 不妨设a 1 为3 度顶点a k 为2 度顶点 ( 1 ) 若a 1 ，a k 相邻，不妨设a k = a 2 ，考察与a l ，i l k 邻接的边和a l + a 2 a t + a 2 n a l + b l ，a 2 + a 3 且a 2 + a 3 ， c l c 2 2 1 验证任意边和属于c ： a f + a “1 = ( 一1 ) 。【( f 一1 ) 1 0 + 1 + ( 一1 ) h 1 “+ 1 1 ) 1 0 + 1 = 1 0 = c 1 i = 1 ，3 ，2 n 一1 a i + 口m = ( 一1 ) 1 o 一1 ) 1 0 + 1 + ( 一1 ) 件1 o + 1 1 ) 1 0 + 1 = 一1 0 = c 2 i = 2 , 4 ，- - ，2 n 一2 a 1 + a 2 。= ( 一1 ) ( 1 1 ) 1 0 + 1 + ( 一1 ) 肋 ( 2 咒一1 ) 1 0 + 1 = ( 2 n 1 ) 1 0 = c 4 山东师范大学钡+ 学位论文 b i + b 川= ( 一1 ) 。 0 1 ) 1 0 + 7 + ( 一1 ) h 0 + i 一1 ) x 1 0 + 7 = 1 0 = c ， i = 1 ，3 ，+ ，2 n 一1 b i + b i + i = ( 一1 ) 。 ( i 一1 ) 1 0 + 7 + ( 一1 ) ”1 【o + 1 1 ) 1 0 + 7 = 一1 0 = c 2 i = 2 , 4 ，2 n 一2 b l + b 2 。= ( 一1 ) ( 1 1 ) x 1 0 + 7 + ( 一1 ) 2 ” ( 2 n 一1 ) 1 0 + 7 】= ( 2 n 一1 ) 1 0 = c 。 2 t l + b 2 女= ( 一1 ) 2 。 ( 2 尼一2 ) 1 0 + 1 + ( 一1 ) 2 ( 2 七一1 ) 1 0 + 7 】= 1 6 = c 3 k = 1 , 2 ，- - - - 一，n 3 ) 验证任意不相邻顶点标号之和不属于s 3 1 ) a 中元素：不妨设a i a j 不相邻 ( 1 ) i ，j 同奇偶： a i + a j 一十2 或a 。+ a 一鹕， 故a j + a j s ( 2 ) i ，j 奇偶互异，且j f j | 1 ： h + 口= l ( 一1 ) i ( i 一1 ) 1 0 + 1 + ( 一1 ) 3 ( j 一1 ) 1 0 h i = ii jl 1 0 c ，c 2 故a ，+ a ，e s 3 2 ) b 中元素验证完全类似 3 3 ) a 与b 间：即验证a ，+ b ，芒s ( 1 ) i ，j 同奇偶： a i + b j 一十2 或a i + b j 一 8 ， 故a j + b j g s ( 2 ) i 为奇，j 为偶( j i + 1 ) ： a i + b j 2 ( 1 ) 1 ( i - 1 ) 1 0 + 1 十( - l y ( i - 1 ) x1 0 + 7 = 一( i - 1 ) 1 0 一l + ( j 一1 ) x1 0 + 7 = ( j - i ) 1 0 + 6 1 6 = c 3 故a , + b j i 岳s ( 3 ) i 为偶，j 为奇： ( a + b j ) = ( i 一1 ) 1 0 + 1 一( j - ) 1 0 7 = ( i - j ) x 1 06 = ( 卜j 1 ) l o + 4 一 4 故a i + b j 芒s 3 4 ) 显然c 间无连边 3 5 ) 考虑c 与a 之间： c + a ，= ( 一1 ) 1 ( i 1 ) x1 0 + 1 + 1 0 1 7 山东师范大学硕上学位论文 i 为奇：c l + a j = 一( i 一2 ) 1 0 1 = 一( ( i - 2 ) 1 0 + 1 )仨s i 为偶：c l + 南= ( i 1 ) x1 0 + 1 + 1 0 = i x1 0 + 1 匹s i 为奇：c 2 + a i = 一1 0 + ( 一1 ) 1 ( i 一1 ) x1 0 + 1 卜( i 1 0 + 1 ) s i 为偶：c 2 + a i l o + ( 一1 ) 1 睁1 ) xl o + 1 1 = 0 2 ) l o + l 萑s i 为偶：c 3 + a i = 1 6 + ( - 1 ) 1 【( i 一1 ) 1 0 + 1 = i x1 0 + 7 一十7 s i 为奇：c 3 + a i = 1 6 + ( 一1 ) 1 ( i 1 ) 1 0 + 1 】一 5 仨s i 为偶：c 4 + a i = ( 2 n 一1 ) x1 0 + ( 一1 ) i ( i 一1 ) x1 0 + 1 2 ( 2 n 一1 、x1 0 + ( i 一1 ) x1 0 + 1 2 ( 2 n + i 一2 ) x1 0 + 1 一 1 仨s i 为奇：c 4 + a i = ( 2 n 一1 ) x1 0 + ( 一1 ) 1 【( i 一1 ) 1 0 + 1 2