（应用数学专业论文）关于（模整）和图的几个结果.pdf

独包声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得( 注：如没 有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：魏建新 导师签字：毒萨玄乞 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密 后适用本授权书) 学位论文作者签名 瓴龟新导师签字：高移坷乙 签字只期：2 0 0 5 年牛月t or 签字日期：2 0 05 ，年钥l f 日 坐查师范太堂硕士学位论文 关于( 模，整) 和图的几个结果 魏建新 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 本文仅考虑有限无向简单图，所用图论记号及术语遵循文献【1 1 9 9 0 年，f h a r a r y 2 提出了和图的概念令表示正整数集，的非空有限 子集s 的和图g + ( s ) 是指图( s ，e ) ，其中e 当且仅当u + u s ，一个图g 称 为和图，若它同构于某个scn 的和图。此时我们说s 给出了g 的一个和标号， 而一个圈g 的和数o ( a ) 是使得g 1 2n k l 是和图的非负整数7 1 的最小值 1 9 9 4 年，f h a x a r y s 又介绍了整和圉、整和数的概念，即把和图、和数定义中 的正整数集换成整数集z 模和图的概念是由b o l a n d 等人f 4 】提出的模和图是取sc 磊。 o 且所有算 术运算均取模m ( t s l + 1 ) 的和图，其中= 0 ，l ，2 ，m l ，一个图g 的模 和数p ( g ) 是使得g u p k l 是模和图的孤立点数p 的最小值这个概念是s u t t o n 等 人( 5 j 提出来的 从实用的角度来看，( 整，模) 和图标号可用作图的压缩表示，即表示图的数据 结构可作为图的一种定义及存储方式。 目前对和图的研究主要集中在两个方面：一方面研究图的( 整) 和数与其它图 参数、图结构的联系；另方面是从一些特殊图类着手，确定它们的和数、整和数 与模和数迄今为止，已经取得了许多成果，提出了一些好的方法，给出了一些一 般性的理论，并且还将和图的概念推广到了超图上 在本文的第一章中，我们主要介绍了关于和图的一些概念、术语、符号，而且 给出了几个关于( 整) 和图与其它图参数、图结构联系方面的定理；在第二章确定 l 山峦师范太学硕士学位论文 了二正则图、皇冠图、残皇冠图。皇冠细分图与优皇冠图的和数以及二正则图、皇 冠图和皇冠图的细分图模和数；在第三章中，我们证明了灌木、叉点距离至少为2 的树及完全二又树，都为整和图 在本文中，主要得到如下定理 定理1 2 1 设s l ，s 2 分别为g u 口( g ) k 1 ，h u 口( 日) k l 的和标号，m a x s t = m ，r a i n s 2 = n ，且( m ，n ) = 1 ，如果2 m a x ( s t f m ) ) m 或r a i n ( s 2 n ) ) 芝2 n ，则 口( g u h ) so ( c ) + a ( h ) 一1 定理1 2 2 设g 为n 阶连通的仅含一个饱和顶点的整和图，则g 的边数m 满足n l m 【垒二墨j 1 定理1 2 3 设整和图g 的团数u ( g ) 3 ，则g 的阶至少为2 w ( c ) 3 定理1 2 4单位图g 的阶最少为知( g ) 一2 定理2 1 1 除a 外所有二正则图的和数均为2 定理2 , 2 1残皇冠图暖o k l 的和数为1 ， 定理2 2 2设n 3 ，则a ( go k l ) = 1 定理2 3 1设n 3 为整数，则口( s ( 瓯o k l ) ) = 1 _ 定理2 3 2 设t 1 4 为偶数，则口( c 二o k f ) = 1 定理2 3 3除q 外的2 正则图、皇冠图、皇冠细分图都是模和图 定理2 4 1c 3 0 k l 的整和数为1 引理3 1 1灌木? s 是整和图 定理3 2 1叉点距离至少为2 的树是整和图 推论3 2 1任何一棵树的细分图是整和图 定理3 3 1完全二叉树是整和图 关键词：( 模，整) 和图；( 模，整) 和数；( 模，整) 和标号； 二正则图； ( 残，优) 皇冠图；灌木；叉点；粘合 分类号： 0 1 5 7 6 2 山东师范大学硕士学位论文 s o m er e s u l t so n ( r o o d ，i n t e g r a l ) s u mg r a p h w e ij i a n x i h 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 l sr e p u b l i co fc h i n a a b s t r a c t a 1 lg r a p h sc o n s i d e r e di nt h i st h e s i sa 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 w i ng 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 yi n p l t h en o t i o no fs u mg r a p hw a si n t r o d u c e db yf h a r a r y 蹦i n1 9 9 0 ，l e tnd e n o t e t h es e to fa l lp o s i t i v ei n t e g e r s t h es u mg r a p hg + ( s ) o faf i n i t es u b s e tscni s t h eg r a p h ( s ，e ) w i t h 虬甜ei f a n do n l yi f 缸+ 副s 。ag r a p hgi ss a i dt ob ea s u n lg r a p hi fi ti si s o m o r p h i ct ot h es u mg r a p ho fs o m escn i nt h i sc a s ew es a y t h a tsg i v e sa ns u ml a b e l l i n gf o rgt h es u n ln u m b e ra ( a 1o fgi st h es m a l l e s t n 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 ogr e s u l ti nas u mg r a p h i n1 9 9 4 f h a r a r yf 3 】i n t r o d u c e dt h ec o n c e p t so f i n t e g r a ls u n lg r a p ha n d i n t e g r a l s u mn u m b e ro fag r a p hw i t hscz ( t h es e to fa l li n t e g e r s ) i n s t e a do fscn m o ds u mg r a p hw a si n t r o d u c e db yb o l a n de ta lnar o o ds u m g r a p hi sas u i n g r a p hw i t hscz m o ) a n da l la r i t h m e t i cp e r f o r m e dm o d u l omw h e r em s i + 1 t i l er o o ds u r dn u m b e rp ( c ) o fgi st h el e a s tn u m b e rpo fi s o l a t e dv e r t i c e sp k is u c h t h a tgup k li sam o ds u mg r a p ht h i sc o n c e p tw a si n t r o d u c e db ys u t t o ne ta l 【5 j 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 eu s e da sac o r n p r e s s e dr e p r e s e n t a t i o no fag r a p h ，ad a t as t r u c t u r ef o rr e p r e s e n t i n gt h eg r a p h ，a n d a na l t e r n a t i v em e t h o df o rd e f i n i n ga n ds t o r i n gg r a p h s n o wt h er e s e a r c ha i m sa tt w oa s p e c t s o n ei st os t u d yt h er e l a t i o nb e t w e e n t h e ( i n t e g r a l ) s l i mn u m b e ra n do t h e rp a r a m e t e r sa n ds t r u c t u r e so ft h eg r a p ht h e o t h e ri sa td e t e r m i n i n gt h es u mn u m b e r ，i n t e g r a ls u mn u m b e ra n dr o o ds u mn u m b e r o fs o m eg r a p hc l a s s e s s o m ea c h i e v e m e n t sh a v eb e e ng o t t e n ，s o m eg o o dm e t h o d a n dg e n e r a lt h e o r e m sh a v eb e e ng o t t e n ，a n dh a v eb e e ne x t e n d e dt oh y p e r g r a p h s 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 cc 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 e sw h i c ha r eu s e di nt h i st h e s i s ，a n ds u r v e y ss o m e , e l a t e dr e s u l t sa b o u t ( i n t e g r a l ) s u mg r a p h s i nt h es e c o n dc h a p t e rw ed e t e r m i n et h e s h i l ln u m b e ro f2 - r e g u l a rg r a p h ，c r o w ng ok 1 ，i n c o m p l e t ec r o w ng r a p h 叹ok 1 ， t h es u b d i v i s i o ng r a p ho fgok 1a n dc o m p l e t ec r o w ng r a p hg no 研a n dm o ds u m 3 幽查堕堇盔堂堡主堂焦迨塞 n u m b e ro f2 - r e g u l a rg r a p h ，c r o w ne nok ia n dt h es u b d i v i s i o ng r a p ho fc 。ok 1 i nt h et h i r dc h a p t e rw ep r o v et h a ts h r u b s ，t r e e sw i t ha l lf o r k sa tl e a s td i s t a n c e2 a p a tla n dt h ec o m p l e t eb i n a r yt r e e sa r ea l li n t e g r a ls u mg r a p h s i n 也i st h e s i sw eo b t a i nt h ef o l l o w i n gt h e o r e m s ， t h e o r e m1 2 1 s u p p o s eg ，ha r en o ts u l ng r a p ha n d l e ts 1 ，s 2d e n o t et h e s u ml a b e l l i n g so fgu 叮( g ) k ia n d 日uo ( h ) k 1r e s p e c t i v e l y ，a n ds u p p o s em a x s l = m ，m i n 岛= 礼a n d ( m ，n ) = 1 i f m i n ( s 2 n ) ) 2 no r2 m a x ( & m ) m ，t h e n 盯( g u h ) o ( a ) + o ( h ) 一1 t h e o r e m1 2 2l e tgb eac o n n e c t e di n t e g r a ls u mg r a p hw i t hn ( 3 ) v e r t i c e s a n dme d g e s i fgh a so n l yo n es a t u r a t e dv e r t e x ，t h e nn l m 【3 n 百2 - 一3 j 一1 t h e o r e m1 2 3 t h es m a h e s to r d e ro fa ni n t e g r a ls u mg r a p hw i t hc l i q u e n u m b e r “j ( g ) 3i s2 叫( g ) 一3 t h e o r e m1 2 4 t h es m a l l e s to r d e ro fau n i ts u mg r a p hi s2 w ( c ) 一2 t h e o r e m2 1 1t h es u mn u m b e ro f2 - r e g u l a rg r a p h sw i t ht h ee x c e p t i o no f c 4i s 2 t h e o r e m2 2 ，1t h es u mn u m b e ro fc ：o k li s1f o ra l ln 3 t h e o r e m2 2 2t h es u mn u m b e ro f gok li s1f o ra l ln 3 t h e o r e m2 3 1t h es u mn u m b e ro fs ( g0k 1 ) i s1f o ra l l 竹3 t h e o r e m2 3 2t h es u mn u m b e ro fg0k ? i s1f o ra l le v e nn 4 t h e o r e m2 3 3 a l l2 - r e g u l e rg r a p h sw i t ht h ee x c e p t i o no fc 4 ，c nok 1a n d s ( c ，1ok 1 ) a r ea l lm o ds h i ng r a p h s t h e o r e m2 4 1t h ei n t e g r a ls u r en u m b e ro fc r o w nc 3ok li s i t h e o r e m3 1 1 e v e r ys h r u bi sa ni n t e g r a ls u mg r a p h t h e o r e m3 2 1 a n yt r e etw i t ha l lf o r k sa tl e a s td i s t a n c e2a p a r ti sa n i n t e g r a ls u mg r a p h c o r o l l a r y3 2 1 t h es u b d i v i s i o no fa n yt r e ei sa ni n t e g r a ls u mg r a p h t h e o r e m3 3 1 a n yc o m p l e t eb i n a r yt r e ei sa ni n t e g r a ls u mg r a p h k e yw o r d s ：( r o o d ，i n t e g r a l ) s u mg r a p h ；( r o o d ，i n t e g r a l ) s u mn u m b e r ；( r o o d i n t e g r a l ) s u ml a b e l l i n g ；2 - r e g u l a rg r a p h ；( i n c o m p l e t e ，c o m p l e t e ) c r o w n ；s h r u b ；f o r k ； i d e n t m c a t i o n c l a s s i f i c a t i o n ：0 1 5 7 6 4 山东师范大学硕士学位论文 第一章基础知识军虮个结构定理 1 1 基础知识 和图的概念是1 9 9 0 年f h a r a x y n 提出来的，它是图的一种标号方法令表 示正整数集，的非空有限子集s 的和图g + ( s ) 是指图( s ，e ) ，其中u ee 当且 仅当“- i - ”s 一个图g 称为和图，若它同构于某个s n 的和图此时我们说s 给出了g 的一个和标号，而且将顶点与其标号不加区分显然若图g 是和图则必 不连通( k 。除外) ，但总可以给g 加上有限个孤立顶点使之成为和图图g 的和数 一( g ) 就是使得图g u n k l 是和图的非负整数n 的最小值特别地，如果一( g ) = 1 ， 则g 称为单位图 g u a ( g ) k z 的和标号称为g 的最优标号如果图g 的最优标 号里含有1 ，这个标号就称为g 的最小标号吼刻划单位图的就是一个重要研究问 题 1 9 9 4 年fh a r a r y a l 又提出了整和图的概念将上述和图定义中的n 换成整数集 合z 即得到整和图、整和数( ( ( g ) ) 、整和标号的定义由定义显然可见( ( g ) a ( g ) ， 并且整和图g 可能连通， 模和图的概念是由b o l a n d 等人【4 】提出的模和图是取scz m 0 ) 且所有算 术运算均取模m ( i s l + 1 ) 的和图s u t t o n 等人f 5 】提出了模和数的概念：一个图 g 的模和数p ( g ) 是使得gup k l 是模和图的孤立点数p 的最小值显然模和图也 可能连通 不难看出，对于一个图g ，有( ( g ) 口( g ) ，p ( c ) sd ( g ) 并且显然一个图是和 图则必是整和图，也一定是模和图 从实用的观点来看，和图标号可用作图的压缩表示，即表示图的数据结构可 以作图的一种定义及存储方法 一般说来，确定一个图的( 模，整) 和数是非常困难的s u t t o n 等人【7 ) 猜测 确定图的模和数是个p 一难的问题 目前对和图的研究主要集中在两个方面： 一方面研究图的和数与其它图参数、图结构的联系，这方面的结果已有很多 s m y t h 8 l 证明了对任意的- - x 于正整数m 都存在着m 条边的和数为o ( n ) 的n 阶 图；还指出若【譬j m 翌警卫，则不存在有m 条边的札阶单位图；若n 一1 7 ns 【等j ，则至少存在一个有m 条边的n 阶单位图 n a g a m o c h i 等【9 1 证明对于 图g = ( v e ) ，有盯( g ) fef 一3f yi ( f o gf 矿1 ) ( f o g 止且1 ；1 二址ffi 卜 矿i 一1 g o u l d 等【1 0 】肯定了存在图g = ( k e ) ，有o ( c ) 0 ( iv1 2 ) ，虽然还未给出这样的 图类现在知道的一类和数“最大”的图类一轮w ，n ，其和数一( 仉，n ) 0 ( ie1 ) 1 2 2 】 山东师范大学硕士学位论文 c h e n 1 证明了任何一个图都是某个连通整和图的诱导子图；同篇文章中c h e n 还 指出除砥外任何一个连通整和图至多有两个饱和顶点( 饱和顶点是指与其它顶点 都相邻的顶点) ，并且确定了含两个饱和顶点的整和图；同时也证明了不含饱和点的 7 阶连通整和图的边数m 满足m 业竽盟在1 1 2 中k r a t o c h v i l 等猜测有结论 o ( c u h ) 口( g ) + o ( h ) 一1 和图研究的另一方面主要是确定某些特殊图类的( 模，整) 和数现在已经确 定了( 参见 2 f a 1 3 2 7 j ) 完全图k 。、完全二分图琢”轮、酒会图氆，。( 即 k 2 。一e ( n k 2 ) ) 、k n 。一e ( n 鲍) ) 、扇f n 、路r 及其补图p n 、圈及其补图 岛及图k 。一e ( 坼) 的和数与整和数i “s m e l n i k o v ，a v p y a t k i n 2 目提出了整半径 的概念并证明了除国外所有二正则图都为整和图在 2 9 ，3 0 】中g s u r e s hs i n g h ，g s a n t h o s h 研究了皇冠图瓯ok l 卿g 的每个顶上都悬挂一条逸而得到的图) 。证 明了除c zok l 外所有皇冠图及其细分都为整和图 m n e l l i n g h a m 3 1 】证明了树 ( k 【除外) 的和数为1s h e n g c h y a n gl i a w 等证明了毛虫是整和图 c h e r t ( 3 2 】提 出了种得到新的连通整和图的方法一粘合法，并用这种方法证明了叉点距离至 少为4 的树及广义星均是整和图，还猜测树都是整和图j b o t a n d ，r l a s k a r 引证明 了n 3 阶的树、n 4 阶的圈及某些完全二部图是模和图m ，s u t t o n 等人在 f 7 1 中确定了轮 的模和数 m ，s u t t o n 等f 3 。】又给出了酒会图扔，n 和啊。的模和 数，窦文卿在【2 0 1 中确定k 。一e ( n 殓) ，r 和一定条件下坼。，k n e ( k ，) 的模和 数 和图的概念已经推广到了超图上1 3 4 , 3 5 】，使得和图理论丰富化，深刻化s o n n t 职 和t e i c h e r t 驯】证明了某些条件下的超树的和数为1 这两位作者【35 】还证明了一定 限制下的超树是整和图，同时也给出了部分完全超图的整和数 本文用g 表示g 的补图，设，是由不同的整数组成的g 的标号边u u e ( c ) u e ( a ) 称为，一正常的，如果对某个”v ( c ) 有f ( u ) 十i ( v ) = ( w ) a 2 1 显见有以下的几个事实 事实1 若，为g 的整和图标号，则m ，也是g 的整和标号，其中m 为非零 的整数 事实2 ，是g 的整和标号当且仅当g 的边是，一正常的，0 的边非，一正 常 事实3r 假设g 为非平凡图，则对于任意的z y ( g ) ，( z ) 0 当且仅当 ( g ) jv ( g ) j 一1 6 山东师范大学硕士学位论文 1 2关于和图结构的几个定理 本节将给出和图与其它图参数、图结构的联系方面的四个定理， k r a t o c h v i l ，m i l l e r 和n g u y e n 在【1 2 1 中提出 猜想a 对于任意两个图g ，日有o ( c u h ) d ( g ) 十o ( h ) 1 g ，日都是和图时上述猜想显然不成立，加上条件“g ，h 都不是和图时”，我 们给出下面的充分条件 定理1 2 1 设g ，h 都不是和图，s 1 ，s 2 分别为g u 口( g ) k 1 ，h u a ( h ) k l 的和 标号，且m a x s l = m ，r a i n s 2 = n ，而m ，n 互质，如果r a i n ( s 2 n ) ) 2 n 或2 m a x ( s l m ) sm ，则有口( g u 日) 口( g ) + a ( h ) 1 证明先设m i n ( s 2 n ) 2 n 下面说明n s l + m s 2 = s 给出了( g u 日) u ( 口( g ) + o ( h ) 一1 ) l 的一个和标号事实上显见有： ( 1 ) r e ( r a i n ( 岛 n ) ) 2 r a n = n ( 2 m a x ( s 1 ) ) ( 2 ) 显然v u ，v s ，若“ e ( g u ) ，则“口是s 一正常的 ( 3 ) v u ， s ，若 e ( g u h ) ，则u u 非s 正常的否则9 w s ，+ ： 若u ，”n s l ，则根据( 1 ) w n s t r a n ，显然这是不可能的；根据( 1 ) 更不可能有 扎， m & ；若u n s , m n ) ，钉m 岛，则 m & ，设“= n u ，u = m u ，叫= m 叫， 其中1 0 。， 岛，u s 1 ，则有n u = m ( 一 7 ) ，由u m 及m ，n 互质，可知这是不 可能的 再设2 m a x ( s 1 m ) ) m ，下面说明n s l + m = s 给出了( g u 日) u ( o ( g ) 十 o ( h ) 一1 ) 耳1 的一个和标号事实上显见有： ( 1 ) n ( 2 m a ( s 1 m ) ) ) m n = r e ( r a i n ( 岛) ) ( 2 ) 显然v u ， s ，若u u e ( g u 日) ，则u u 是s 一正常的 ( 3 ) v u ，u s ，若u u e ( 百口面) ，则u 非s 一正常的否则j s ，u + v = w 若 u m 岛，则根据( 1 ) t j m 岛，显然这是不可能的；根据( 1 ) 更不可能有u ， n s l ； 若 m 岛，u n s l n m ) 则w m 函，设u = 札u ，口= m 7 ， = m 伽，其中 u j7 ，u ， s l ，则有n “= m ( w 一 ) ，由 o ，s 一= 蚓s s ，s o ) 不妨设 i s i i s + i 显然n = 3 时g 岂g 卜1 ，0 ，2 ) ，结论成立 当n 4 时，则i s l 2 设s 一= o i ，a 2 ，8 女) ，s + = 6 1 ，b 2 ，一一 ) ，其中 a l 0 2 。k ，h + k = n 一1 因为t = 1 ，2 ，一1 时0 t + a j a i ，所以d ( a 1 ) 墨 f i 一1 ) + ( h + 1 ) = h 十i ，因为d 七+ d ， d 一i ，所以d ( a k j ( 七一2 ) + ( h + 1 ) = h + 七一l ， 于是坠】d ( a ：) 茎e 辟k - l i ( h + i ) 十( h + 七一1 ) = 丛笔出+ k h 一1 情形1f s + l = 0 此时是= n l ，h = o m = 曩1l 厶h 仁l d ( o i ) + d ( o ) ) 曼 t 妊三4 三坦一1 + ( n 一1 ) 1 = 翌二丰型l s 下3 n 2 - 3 一1 情形2j s + l = 1 此时k = n 一2 ，h = 1 因为g 仅含一个饱和顶点0 ，所以d ( 6 1 ) sn 一2 ，于是 t n = 孙1 厶仁kld ( a i ) + d ( 6 1 ) + d ( o ) ) ( 且山+ k h l + 礼2 + 札一1 ) = 也二掣 情形3i s + l 2 则有；：ld ( b j ) 丛! 笋卫+ k h 一1 于是r n = ；( ；：1 d ( b j ) + 坠1d ( q ) + d ( o ) ) ( 丝号尘+ k h 一1 + 丝唑+ k h 一1 + 竹一1 ) 3 ( n - 1 ) 2 8 - f 6 ( n - 1 ) 一1 = 3 n 8 - 一3 1 而显然可见n 3 时垃掣一j 巫兰擎坦t 3 n 2 - 3 一1 由g 是连通的故下界是平凡的，定理得证 我们可以给出几个可以取到上限的例子不难验证当n = 3 ，4 ，5 ，6 ，7 ，8 时s 】= 一l ，0 ，2 ) ，岛= 一2 ，0 ，1 ，2 ) ，岛= - 2 ，一1 ，0 ，l ，2 ，& = - 3 ，一1 ，0 ，1 ，2 ，3 ，民= 卜3 ，- 2 ，- 1 ，0 ，1 ，2 ，3 ) ，风= - 3 ，- 2 ，- 1 ，0 ，1 ，2 ，3 ，4 ) 上的整和图分别为对应的极图 而下限的极图，对任意的n 可以取星图晶= g + ( s ) ，其中s = o ，l ，3 ，2 n 一1 ) 另外我们再给出下面的两个与团数有关的结论 定理1 2 3 设整和图g 的团数u ( g ) 3 ，则g 阶最少为2 w ( g ) 一3 证明记n = u ( g ) ，s = a u 口是g 的整和标号，其中a = 如l ，。l 是g 的一个n 阶团的标号，且a 1 a 2 1 ，啦 0 ) u o 。十a jj o ) ，于是ibi n 一3 ，iv ( c ) 1 22 n 一3 下面给出两类团数为n 、阶为2 n 一3 的整和图 第一类，此类图含有1 个饱和顶点 n 为奇数时， 令s = ( n 一2 ) ，一( n 一3 ) ，一，- 1 ，0 ，1 ，n 一3 ，n 一2 ) 8 山东师范大学硕士学位论文 n 为偶数时， 令s = 一( 乱一2 ) ，一( 钆一3 ) ，一l ，o ，1 ，n 一3 ，珏一2 ，n l 易见卜孚，- 1 ，0 州1 一，孚) 及 孚，一1 ，0 h 1 一，字，g ) 分别是g + ( s ) 的n 点团 第二类，这类图含有2 个满度顶点 令s = 卜1 ，0 ，1 ，2 n 一5 ) 易见g + ( s ) 中的一个n 点团为卜1 ，0 ，l ， 一 3 ，n 一2 ) 定理1 2 4单位图g 的阶数最少为2 w ( g ) 一2 证明记n = u ( g ) 、s = a u b u c 是g u k l 的和标号，其中a = a l ，a 2 ，n n ) ， 是g 的一个n 阶团的标号，且o l a 2 a 。易见n 2 ，b a n 十qy = 1 ，2 ，n 一1 c ) ，于是1bi n 一2 ，iv ( c ) i 2 n 一2 下面给出一类团数为n 阶为2 n 一2 的单位图 令s ：f 1 ，2 ，n ，n + 1 ，2 n 一2 ，2 n 1 ) 易见g + ( s ) 中的一个n 点团为 1 ，2 ，一，n ) f h a r a r y 3 】介绍了一类非常有意义的和图g + ( 。) ，其中n n = 1 ，2 ，n ) ，并 且说虽尽了很大的努力仍未找到刻划g + ( n n ) 的结构的简洁方法由定理1 2 4 我 们可以给出g + ( 。) 一个简洁的刻划当n = 2 m 一1 为奇数时，g + ( k ) n ) 是 团数为m 的阶最小的单位图；当n = 2 m 为偶数时，g + ( ) n ) 是团数为m 的 最小奇数阶单位图 9 些壅竖堕盔堂塑圭堂焦望皇 第二章几类图的和数 2 1二正则图的和数 在 2 8 中l sm e l n i k o v ，a v p y a t k i n 给出了下面的结论 定理b除q 外所有二正则图都为整和图 本节我们将证明除。外所有二正则图的和数都为2 弓i 理2 1 1 【目口( q ) = 3 ；口( c k ) = 2 ，n 3 ，n 4 引理2 1 2 口( c t u q ) = 2 ，其中t = 3 ，4 ，5 ，6 ，7 证明令s 1 = f o ，b ，a + 3 b ，o + b ，2 b ，2 a + 3 6 ，n + 4 b ，2 a 十5 b ，3 a + 7 6 ) ，岛= 口，b ，2 b ，f l , + 4 b ，n + 6 ，3 b ，2 a + 4 b ，n + 6 b ，2 a + 7 b ，3 a + 1 0 b ，s a = 口，b ，a + 3 b ，6 b ，a + 4 b ，2 b ，a + b ，d + 9 b ，“+ 6 b ，2 a + 1 0 b ，2 a + 1 5 b ，函= n ，b ，d + 3 6 ，6 b ，n 十4 6 ，2 6 ，n + b ，a + 9 b ，2 a + 1 0 b ，o + 6 b ，3 a 十1 6 b ，3 8 十1 9 bs s = n ，b ，口+ 3 b ，6 b ，8 + 4 b ，2 b ，。+ 6 ，o + 9 b ，2 a + 1 0 b ，3 a + 1 9 b ，g + 6 b ，4 n + 2 5 b ，5 a + 2 9 b 其中0 n b 2 a ，则可以证明s l ，岛，岛，s 5 分别给出了 ( 仍u q ) u2 k 1 ，( 瓯u c 4 ) u2 k 1 ，( c 5 u q ) u2 k 1 ，( 瓯u c 4 ) u2 k 1 ，( c 7 u 瓯) u2 k t 的 一个和标号 为此我们验证s l 是( q u q ) u2 k 1 的一个和标号，其它情形类似给出 事实上，显见n b a + b 2 b a + 3 b 2 a + 3 b a + 4 b 2 a + 5 b 3 n + 7 b ( 1 )n + b s ；a + ( o + 3 b ) = 2 a + 3 b s ；2 b o 十( o + b ) = 2 a + b a + 3 b ； a + 4 b a + ( a + 4 b ) = 2 a + 4 b 2 a 十5 b ；a 十4 b a + ( 2 a + 3 b ) = 3 a + 3 b 2 a + 5 b ； 2 0 + 5 6 o + ( 2 a + 5 b ) = 3 a + 5 b 3 0 十7 6 ( 2 )2 b b + ( a + b ) = n + 2 b a + 3 b ；b + + 3 b ) = 十4 b ；2 b b + 2 b = 3 b c , + 3 b ；a + 4 6 b + ( n 十4 b ) = o + 5 b 2 a + 5 b ；十4 b b + ( 2 a + 3 b ) = 2 a + 4 2 n + 5 b ；2 a 十5 b 3 a + 7 b ( 3 )o + 4 b ( a + 3 b ) + ( 0 + b ) = 2 a + 4 b 2 a + 5 b ；a + 4 b ( o 十3 6 ) 十2 b = a 十5 b 2 。十5 b ；2 a + 5 b ( n + 3 b ) + 扣+ 4 b ) = 2 a + 7 b 3 a + 7 b ；2 a 十5 b + 3 b ) + ( 2 a + 3 b ) = 3 d + 6 b 3 a 十7 6 ；3 n + 7 b ( o + 3 6 ) + ( 2 n + 5 b ) = 3 a + 8 b ( 4 )2 b + ( o + b ) = o + 3 b s ；( n + 4 6 ) + ( n + b ) = 2 a + 5 b s ；f l , 十4 b ( 2 “p3 b ) + ( a 十b ) = 3 a + 4 6 2 a + 5 b ；2 a + 5 b ( 2 a 十5 6 ) + ( a + b ) = 3 a + 6 b 3 a + 7 b ( 5 )2 a + 5 b = 2 b + ( 2 a + 3 b ) s ；2 a + 5 b 2 b + 缸+ 4 6 ) = n + 6 占 3 a + 7 b ； 2 口+ 5 b 2 b + ( 2 a + 5 b ) = 2 a + 5 b 3 口+ 7 6 些查盟焦盔堂堡堂焦鲨窒 以上证明说明有a ( c t u c 4 ) 茎2 又显然c r ( c tu q ) 2 ，故而口( q u q ) = 2 引理2 1 3口( g u q ) = 2 ，其中n 8 。 证明令s = f b l ，b 2 ，b 3 ，k ，口1 ，n 2 ，n 3 ，0 4 ，0 5 ，口6 ，0 7 ，0 8 ，o n ，c l ，c 2 ) ，其中b l = 日，b 2 = b ，6 3 = o + 3 b ，6 4 = 6 6 ，1 = 口+ 6 b ，a 2 = o 埘6 ，0 3 = 2 b ，a 4 = o + b ，a 5 = o + 9 6 ，a 6 = 2 。+ 1 0 b ，口7 = 3 a + 1 9 b ，a 8 = 5 a + 2 9 b ，n 9 = n 7 + a 8 ，n n 一1 = n 一3 + o n 一0 ，o n = d n 一2 + 札n l ，c l = 口n + g 1 ，c 2 = n n + o s l 下面证明g + ( s ) 竺( 瓯uq ) u2 k 1 ，n 8 ，事实上结合引理2 1 1 ，2 1 3 只须证 明 ( 1 ) ：若( 啦，n ) 簪e ( g u 瓯) ，则毗+ o ，隹s ( 2 ) ( b t ，6 3 ) ，( 幻，b 4 ) ge ； ( 3 ) ：( n 。幻) 隹e ( 4 ) ：( o i ，勺) ，( b i ，勺) 隹e 事实上，易见6 i 6 2 8 4 8 3 6 3 8 2 b 4 n 1 8 5 口6 8 n 一1 o n c l c 2 。 ( 1 )1 墨isj 7 时， 啦+ o j 0 6 + a 7 = 0 8 ，1 i 茎7 ，8 j n 一1 及 8 isj 7 l l 时， q o l + q 吖一1 + 即= q + 1 ，而且j = 礼，15ts4 时 n n n z 十o n c l ，j = 礼，5 i 墨n 一1 时c l n i + o n c 2 ，于是( 1 ) 得证 ( 2 )显见b l + b 3 ) = 2 a + 3 b n 6 ，6 2 + b 4 = 7 b a 6 ( 3 ) 显然i57 时， a i + 如s 口7 + 如= 3 a + 2 5 b a 8 ；7 i n 一1 时， oz a i + 幻 啦+ o 卜1 = 啦+ l