（运筹学与控制论专业论文）两类新的整数和图.pdf

摘要 和图的概念最初是由h a r a r y 提出的令表示正整数集合，z 表示整 数集合，对上的有限子集s ，定义和图g + ( s ) = ( s ，e ) 其中s 是点集合， e 是边集合，且对n ，o u v e 骨“+ 口s ，图g 称为和图当且仅当存 在有限子集s n + ，使得g 同构于g + ( s ) 对任意图g ，都存在非负整数m 使得g u m k l 是一和图使g u m k l 是一和图的最小的非负整数m o 为g 的和数，记为a ( q 整数和图g + ( s ) 的定义同和图的定义，其唯一差别是用 scz 替换scn + 整数和数( ( g ) 定义为使g t os k l 成为整数和图的最小 的非负整数8 方便起见，整数和图记为f i - g r a p h 本论文由五部分组成第一章是对本论文所涉及的问题的背景、进展以及 所得结果的一个综述在第二章和第四章中，我们分别给出并证明了一类新的 整数和图第三章我们用另外一种方法证明了所有的奇圈都是整数和图，同时 解决了文献【3 】中提出的一个问题第五章是用前面的结果否定了h a r a r y 的 两个猜想，并对前面的内容做一个小节 另外，为了更为直混地反映整数和图的标号，在本文给出了一些具体的图 的标号 关键词：和图；整数和图；c a t e r p i l l a r ；g r i p l i k et r e e 硕士学位论文 m a s t e r st h e s i s a b s t r a c t t h e c o n c e p t o f t h e ( i n t e g r a l ) s u mg r a p h s w a si n t r o d u c e db yh a r a w 1 e tn + d e n o t et h es e to fp o s i t i v ei n t e g e r s ，t h e ( i n t e g r a l ) s u mg r a p hg + f s ) o faf i n i t e s u b s e tscn ( z ) i st h eg r a p h ( s e ) w i t h 让 ei fa n do n l yi f 札+ v s a g r a p hg i sc a l l e da n ( i n t e g r a l ) s u mg 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 m g r a p hg + ( s ) o f s o m esc n + ( z ) t h e ( i n t e g r a l ) s u mn u m b e r o fa g i v e ng r a p h gi 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 no x t d e dt og r e s u l ti n a n ( i n t e g r a l ) s u mg r a p h f o rc o n v e n i e n c e ，a ni n t e g r a ls u mg r a p hi sw r i t t e na s ，一g r a p h t h i sp a p e ri sm a d eu po ff i v ep a r t s f i r s t l y , s e c t i o no n ei sa ni n t r o d u c - t i o nt ot h eb a c k g r o u do ft h er e s e a r c ha n dt h er e s u l t sw eg a i ni nt h i s p a p e r ， s e c t i o nt w oa n df o u ra r ea b o u ts o m en e wc l a s s e so f ，- g r a p h ，i ns e c t i o n t h r e ew e p r o v et h a ta l lt h eo d dc y c l ea r ei n t e g r a ls u mg r a p hb yt h eo t h ew a y i nt h es a a - r l et i m e ，w es o l v eap r o b l e mp o s e db yb a o g e nx u i nf a l i ns e c t i o n f i v ew ed i s p r o v et w oc o n j e c t u r e so fh a r a r y s i na d d i t i o n ，s o m ef i g t u r e sa r e g i v e nt oe x p l a i nt h el a b e l l i n gi n t u i t i v l y k e yw o r d s ：s u mg r a p h ；i n t e g r a ls u l ng r a p h ；c a t e r p i l l a r ；g r i p - l i k et r e e i i 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：i 司会净垒 日期：o 孓年月i j 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 作者签名：同会验 日期：孙浒6 月日 导师签名乃痧趁 日期：府，月7 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本 人的学位论文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章 程”中的规定享受相关权益。圃亟迨塞堡童后进卮；旦坐生；旦二生；旦三生 蕉查! 作者签名：闸会论 日期：为。 年6 月f 日 导师签名名易建 日期：庐哆年占月j ，日 硕士学位论文 m a s t e r st h e s j s 第一章引言 本文中用到但未说明的的符号和术语，我们参照 1 和【2 】 1 1 整数和图的研究背景和现状 自从h a r a r y 提出了( 整数) 和图的概念之后就有很多关于( 整数) 和图的 结果h a r a r y 在 1 证明了所有的路和所有的匹配都是整数和图吴健强在 f 2 中证明了一些c a t e r p i l l a r s 及m r 是整数和图，许宝根在 3 3 中发现了一 类特殊的树是整数和图陈志波在 4 】中证明了顶点数n 4 的完全图的整数 和数等于2 n 一3 何文杰在f 6 中给出了完全二部图的和数及整数和数王雁 在【7 中估计了完全二部图的和数及整数和数l s m e l n i k o v 和a v p y a t k i n 在 8 中证明了除国的所有2 一正则图都是整数和图，并且对于任意的正整数 r 均存在一个r 一正则的整数和图陈志波在【9 】中介绍了如何在给出的整数 和图的基础上构造新连通的整数和图与此同时也有许多问题有待解决，本文 将证明一些g r i p - l i k et r e e s 和m 凰，都是整数和图另外，还解决了许宝根在 3 1 中提出的一个问题，同时否定了h a r a r y 的两个猜想 我们按照 1 中定义的概念和术语，令+ 表示正整数集，则定义在胪 的有限子集s 上的和图g + ) 即是图( s ，e ) 其中s 是点集合，e 是边集 合，且对札，u s u v e 兮“+ v s ，图g 称为和图当且仅当存在scn 使得g 同构于g + ( s ) 对任意图g ，都存在非负整数m 使得g u m l ( 1 是一和 图，则我们称满足g u 讥硒是一和图的最小的非负整数m o 是g 的和数，记 为盯( g ) 整数和图g + ( s ) 的定义同和图的定义，唯一差别是用scz 替换 sc n + 整数和数f ( g ) 定义成为最小的非负整数8 ，其中g us 硒是整数和 图方便起见，整数和图记为r - g r a p h 显然，有定义知，对任意的图g 均有e ( g ) 冬口( g ) ，而且g 是j - g r a p h ，当且仅当e ( g ) = 0 另外，t 称 作一个c a t e r p i l l a r 如果丁7 是一条路( 其中是由p 去掉所有的叶子得到的) 下面两个结论是h a r a r y 在f 1 中提出的 1 定理，1 ，对于任意的正整数扎，圈g 满足盯c g ，= i ：三! 定理1 1 2 对于任意的t t 1 ，只是i 厂一g r a p h 在这里再给出我们后面证明会用到的两个定理： 定理1 1 3 ( 吴健强【2 1 ) 每个c o m b 都是，- g r a p h 定理1 1 4 ( 许宝根 3 】) 所有的t h r e e - p a t ht r e e s 都是，- g r a p h s 12 本文的主要结论 在文献( 1 - ( 3 l 的主要结论的基础上，本文将整数和图进一步推广，证明 了g r i p - l i k et r e e 和i n k l ，都是厂g r a p h s ，同时否定了h a r a r y 的一个猜想 ( 其中g r i p - l i k et r e e 的定义见第二章) 定理2 2 1 如果m + n 4 ，则所有的g r i p - l i k et r e e sp ( 3 ；m ，礼，t ) 都是i 厂 g r a p h s 定理4 2 1 任意两颗星的并是j 。- g r a p h 定理4 3 1 对于任意的正整数m ，m k l ，是r - g r a p h 结论5 3 在第二章中，令t o w n 4 ，则g r i p - l i k e t r e e t = p ( 3 ；m ，n ，t ) ( 4 ) 是r - g r a p h ，但它不是c a t e r p i l l a r 因此猜想5 1 不成立 在文献 3 中给出了当佗= 3 ，5 ，7 时，圈g 可以被标成整数和图，然后 许宝根提出一个问题：是不是所有的奇圈都能标成整数和图呢? 本文的第三 章对该问题做了一个完整的解答，同时也否定了h a r a r y 的另一个猜想 2 硕士学位论文 m a s t e r st h e s i s 定理3 2 1 如果扎奇数，则圈g 是j e g r a p h 结论5 5 综合定理1 1 1 和定理3 2 1 知猜想5 2 不成立 3 第二章g r i p l i k et r e e 在本章中，我们研究一些特殊的g r i p - l i k et r e e ，首先在第一节给出g r i p l i k et r e e 的概念，第二节具体证明了有两类g r i p - l i k et r e e 是整数和图 2 1g r i p - l i k et r e e 的定义 定义2 1 1 树r 称作是一个g r i p l i k et r e e ，如果t 是由具有一个公共端 点的4 条路组成，并且有一条路的长度为2 供冲我们稚这条路为9 而圳它是 树的一种特殊情形若四条路分别记作p 3 ，r ；，r ，r ，则这个g r i p l i k et r e e 便 记作，p ( 3 ；m ，7 t ，t ) 其中顶点数为m 的路记为p ( a 1 ，a 2 ，。) 2 2 某些g r i p - l i k et r e e 的讨论 定理2 2 1 如果m - 4 - n 4 时，下面证明p ( 3 ；2 ，2 ，t ) 是，一g r a p h 其中尸( 3 ；2 ，2 ，t ) 的结 构见图1 我们对p ( 3 ；2 ，2 ，t ) 的顶点标号如下( 在本文的证明中标号有时也代表点) ： l ( c ) = 4 ，1 ( c t 一1 ) = 1 ，f ( 岛) = f ( 矗+ 2 ) 一f ( 岛+ 1 ) ，( i = 1 ，2 ，t 一2 ) j ( q 2 ) = l ( c 2 ) 一f ( c 1 ) ，f ( d 2 ) = l ( a 2 ) 一f ( c 1 ) ( 2 ，1 ) l ( d 3 ) = 1 ( c 1 ) 一f ( d 2 ) ，f ( 6 2 ) = 一l ( d 3 ) 5 硕士学位论文 m a s t e r sn l e s i s 则我们得到序列s = ( f ( c 1 ) ，f ( c 2 ) ，f ( c t ) ，2 ( 。2 ) ，l ( b 2 ) ，l ( d 2 ) ，l ( d a ) ) 具有下 面的性质： ( 1 ) 对任意的l 曼ist 一2 都满足2 ( q ) - f ( c t + 1 ) 0 ，l ( b 2 ) ，t ( d 2 ) 0 ，l ( b 2 ) l ( a 2 ) 0 ，l ( b r ) l ( c 2 ) 0 j ( n 2 ) i ( d r ) 0 ，l ( a r ) l ( d a ) i + 1 由( 2 1 ) 及 性质( 3 ) 知【f ( q ) + f ( o ) f f f ( c f ) f + f f ( 勺) fsf f ( c 1 ) f 十 z ( c 2 ) f = f f ( ) f i l ( d 3 ) l = i l ( b 2 ) 1 则有l ( c 1 ) + l ( d 3 ) l ( b e ) 对于f ( d 2 ) + t ( a 2 ) ，由( 2 1 ) 及性质( 2 ) ，( 3 ) 知l l ( d e ) + l ( a 2 ) | = l l ( d e ) 14 - 1 f ( 0 2 ) l f l ( c 1 ) | 4 - l l ( d 2 ) l ：i l ( d 3 ) i = i ? ( b ) i 则有l ( d 2 ) 4 - l ( a e ) f ( 6 2 ) 对于f ( 。2 ) 4 - l ( d 3 ) ，由( 2 1 ) 及性质( 2 ) ，( 3 ) 知l i ( a e ) 4 - l ( d 3 ) 1 l t ( b 2 ) = l ( d 3 ) 1 再由性质( 3 ) 知它们都不是标号由( 2 1 ) 知j ( b 2 ) 4 - l ( d 3 ) = 0 ，由于0 不存在 于标号中，因此f ( 6 2 ) 4 - l ( d 3 ) 显然不是标号 接下来我们考察l ( 6 2 ) 4 - 2 ( q ) ，其中1 0 时，由( 2 1 ) 知l z ( c 。) 4 - f ( 6 2 ) j | t ( b e ) l = l f ( d 3 ) i 则由性 质( 3 ) 知l ( b 2 ) 4 - f ( 岛) 不是标号 ( i i ) 当l ( b e ) f ( 臼) 0 时，由( 2 1 ) 及性质( 3 ) 知， i2 ( c 。) + l ( b z ) l = | f ( c ：) 一2 ( d 。) l = l2 ( d a ) l i l ( c i ) l l l ( d 2 ) | 则有lc ( d 2 ) l 4 由定理2 2 1 易知，当m + n 5 时结论成立当m + 几三5 时，对 尸( 3 ；m ，扎，t ) 标号如下： l ( a 1 ) = 1 ，l ( a 2 ) = 2 ，l ( a i ) = l ( a l 一2 ) 一l ( a i 一1 ) ，( i = 3 ，4 ，m ) ； 2 ( 6 】) = i ( a 。) ，l ( b 2 ) = z ( 口。一1 ) 一l ( 口。) ， f ( k ) = l ( 。m 十t 一3 ) 一1 ( a m + i2 ) ，( i = 3 ，4 ，n ) ； f 。们 l ( c x ) = f ( 口。) ，f ( c 2 ) = 2 拉( 6 。) f ，z ( q ) = z ( g 一2 ) + f ( c 卜1 ) ， 。 ( i = 3 ，4 ，t 一1 ) ，f ( q ) = l ( a 。) 一f ( c t 一1 ) ； z ( d 1 ) = z ( 盘。) ，l ( d 2 ) = 一l ( c t 一1 ) ，l ( d a ) = z ( c 一2 ) + z ( c 一1 ) 则我们得到序列s = ( f ( 。，) ，2 ( 2 ) ，l ( a 。) ，f ( 幻) ，t ( b 。) ，f ( c 2 ) ，j ( c ；) ，l ( d z ) l ( d 3 ) ) 具有以下性质： ( 4 ) 2si m 时，f ( 。) l ( a i + 1 ) 0 ；l js 时，z ( ) ? ( b + 1 ) 0 ( 5 ) z ( 口。) 0 时，序列( f z ( 盘s ) f ，f z ( 。2 ) f ，f f ( 0 4 孔f f ( g 5 汜，f z ( n 。) f ，f f ( 6 2 ) f ( k ) ( c 2 ) ( c 3 ) j ，j l ( c t 一。) l ，i f 池) i ，i j ( c t 1 ) l ，l ? ( 如) i ) 是严格单增的 ( 6 ) l ( c t ) i f ( d 2 ) l 2 1 t ( b 。) i 且l ( d 2 ) i z ( d 2 ) l 2 1 t ( b 。) i 且l ( d 2 ) 一2 1 l ( b n ) 1 ( 8 ) 序列( i ( c 3 ) 一! ( c 2 ) l ，1 1 ( c 4 ) 一l ( c 3 ) i ，l ( c ) 一f ( c f _ 2 ) i ) 是严格递增 的 性质( 4 ) 由标号2 2 很容易被验证下面我们证明性质( 5 ) ，( 6 ) ，( 7 ) 及( 8 ) 性质( 5 ) 的证明：从( 2 2 ) 易知序列( 1 3 ) 1 ，l l ( a 2 ) l ，i l ( 。4 ) l ，l ! ( n 5 ) i ，l j ( 。) l ， f z ( 6 。) h ，f f ( 6 。) f ，i f ( c 3 m ，f l ( c t 一) f ，f z ( d 3 ) f ) 是严格递增的下面将( c 2 ) ，z ( c t ) ， l ( o ，) 及z ( d z ) 插入到此序列中使得到的序列仍然是严格递增序列 如果f ( ) l ( c 2 ) j ( c 3 ) 再由性质( 4 ) 我们的 到i f ( c a ) f l f ( c 2 ) f f f ( c 3 对于f ( c ) 由性质( 4 ) 及标号( 2 2 ) 知 i z ( c t ) i = - l ( c t ) = l ( c t 一1 ) l ( o ) = f ( c 一1 ) 一2 ( 。m ) l ( c t 一1 ) 另外有i f ( q ) f = f ( q 一，) 一l ( a 。) f ( q 一1 ) + l ( c t 一2 ) = f ( d 3 ) 贝扩苜l ( c t 1 ) i t ( c d i z ( d 3 ) ，即l f 池一) l f ( c t ) l l ( c 2 ) 且有l ( c 2 ) = 2 1 f ( b 。) i 则有l f ( c 3 ) i i l ( c 2 ) l i f ( k ) | 对于c 。，由性质( 4 ) 及标号( 2 2 ) 知i f ( q ) i = - l ( c t ) = l ( c t 一1 ) 一z ( 。) l ( c t 一2 ) + f ( c 1 ) 一l ( a 。) = l ( c f 一2 ) 则有l f ( 白一1 ) i l l ( c t ) j i j ( c 瑚) 卜 因此，当f ( n 。) 0 时，序列( j f ( ) l ，i f ( 2 ) j ，j f ( 口4 ) j ，j ：( 吼) j ，j f ( 口。) j ，j f ( b ：) l 9 硕士学位论文 m a s t e r st h e s i s ，j f ( k ) i ，i f ( c 2 ) l ，i z ( c 3 ) l ，l f ( 白一2 ) i ，z ( c t ) l ，iz ( q 一1 ) l ，i f ( d 3 ) 1 ) 是单调递增的 所以性质( 5 ) 成立 性质( 6 ) 的证明：由标号( 2 2 ) 及性质( 5 ) 知， f ( c t ) = l ( c 1 ) 一f ( 白一1 ) l ( c 1 ) 一l ( c 4 ) = l ( c 1 ) l ( c 2 ) 一l ( c a ) f ( 岛一1 ) = l f ( d 2 ) l l ( c 2 ) = 2 l f ( ) | 又因为f ( d 2 ) f ( c 2 ) = l ( c 4 ) 一l ( c 3 ) l ( c a ) = l ( c a ) 一f ( c 2 ) 因此性质( 8 ) 成立 下面我们回到定理2 2 2 的证明由性质( 5 ) 知l ( d 2 ) = 一f ( q 一1 ) 及l ( a 1 ) = 一f ( 口。) 显然l ( d 2 ) ，l ( a a ) 不同其他标号因此序列s = ( f ( 。，) ，t ( a 。) ，l ( a 。) ， z ( 6 2 ) ，f ( k ) ，2 ( c 2 ) ，z ( 吼) ，f ( d 2 ) ，f ( 如) ) 中的元素互不相同 现在我们验证t = p ( 3 ；m ，礼，t ) ( 其中t 4 ) 中所有相邻两点的标号和仍 然是t = p ( 3 ；m ，n ，t ) 的标号由( 2 2 ) 知， m + n 4 时，有l ( a 1 ) + l ( a 2 ) = 1 + 2 = 3 = l ( a 4 ) 是一个标号 f ( 吼) 十2 ( 。件1 ) = l ( a l 一1 ) ，2si m 一1 2 ( 6 1 ) + f ( 6 2 ) = z ( o 。) + l ( b 2 ) = l ( a t 一1 ) z ( ) + 2 ( + 1 ) = f ( b 一，) ，2 j n 一1 0 硕士学位论文 m a s t e r st h e s i s l ( c k ) + l ( c k + 1 ) = l ( c k + 2 ) ，1 茎k 茎t 一3 l ( c 一2 ) 十l ( c t 一1 ) = f ( d 3 ) 1 ( c t 一1 ) + j ( c t ) = f ( q 1 ) + t ( c 1 ) 一l ( c 一1 ) = e ( c 1 ) 1 ( d 1 ) + l ( d 2 ) = l ( c 1 ) 一f ( q 一1 ) = f ( 岛) 1 ( d 2 ) + f ( 如) = 一l ( c t 一1 ) + i ( c t 一2 ) + f ( q 一1 ) = z ( q 一2 ) 因此，t = p ( 3 ；m ，n ，t ) ( 其中t 4 ) 中所有相邻两点的标号和仍然是 t = p ( 3 ；t t t ，t ) 的标号 下面我们验证t = p ( 3 ；m ，t t ，t ) ( 其中t 4 ) 中所有不相邻两点的标号和 不是标号根据我们的标号规则知，对于每一个f ，r ，r 而言，比如r ：的 任何不相邻的两点的标号和都不再是p 竹；的标号因为它的标号是按照被标 成，一g r a p h 的标号规则得到的( 参见 1 _ 4 ) 因此我们只需要验证下面的 三种情形： 情形1 检验p 3 中所有不相邻两点的标号和不是t = 尸( 3 ；7 n ，佗，t ) ( 4 ) 中 点的标号( 或者说不存在于标号( 2 2 ) 中，或简称不是标号) 如果l ( d 1 ) 0 ，则有l ( d 1 ) + l ( d 3 ) f ( d 3 ) ，由性质( 5 ) 知f ( d 1 ) + f ( d 3 ) 不是 标号 如果l ( d 1 ) l ( c t 一1 ) 一z ( 6 1 ) = f ( c t 一1 ) 一l ( c 1 ) = f f ( 岛) 1 则有f f ( q ) i f ( d 1 ) + l ( d 3 ) i + i 由 1 】中的结论我们直接可知z ( 。；) 4 - l ( a j ) f ( “) ，因此l ( a 。) q - l ( a j ) 不是 路r 中点的标号 由性质( 5 ) ，( 6 ) 及( 2 2 ) 式知f 她) + f 门) i + 1 由【1 中的结论我们直接可知f ( 6 1 ) + f ( ) t ( a k ) ，因此f ( 玩) + f ( 6 ，) 不是 路p m 中点的标号 由性质( 5 ) 及( 6 ) 知，f ( b 。) + f ( b ) z ( c ) ，其中2 st ，因为z ( 玩) + ( 6 j ) i + 1 _ j l f ( k ) j 则它不是r 及只。 中点的标号另一方面我们有 0 2 ( q ) + j ( 勺) sf ( 岛) + l ( c t 一1 ) f ( q 一2 ) + ! ( c 一1 ) = f ( d 3 ) 结合l ( d 2 ) 0 且佗= 1 则 f ( q ) + z 渔) = 一f f ( k ) f = 一f ( 6 ) ，显然不是标号所以z ( q ) + l ( c 1 ) 4 ) 中点的标号( 或简称不是标号) 分六种情况讨论 ( i ) 对于任意a i p ，b r ，我们考虑l ( a i ) + l ( b j ) ，其中1si m ，2 茎 jsn ，因为当i = m 或j = l 时a i 和如在同一条路上，而两点在同一条路 的情况我们前两种情形已经证明过 由于斥。和r 上的标号可以看作是同一条路的标号，因此z ( 。；) + 2 ( b ) 不是r ，或r 上点的标号 由性质( 5 ) ，( 6 ) 及( 2 2 ) 知，2 ( 啦) + f ( 每) 2 i t ( b , 。) f f 2 ( ) ，其中2 茎七t 即有l ( a i ) + 2 ( 幻) f ( c ) ，其中2 k t 因此2 ( o 。) + z ( b j ) 不是r 上点的标 号。 1 3 硕士学位论文 m a s t e r st h e s i s 另外，由性质( 7 ) 知f ( ；) + l ( b j ) l ( d 2 ) ，z ( d 3 ) 因此f ( 。) + t ( b j ) 不是p 3 上点的标号 所以对于任意的1 i m ，2 墨j 兰n ，l ( a i ) + t ( b j ) 都不是标号 ( i i ) 对于任意的o , i f l m ，勺p t ，我们考虑f ( o 。) + f ( 勺) ，其中1 i 2 i t ( k ) l f f ( 6 。) i = i f ( ) l 和l ( a 1 ) + f ( 白) 茎l ( a i ) + l ( c t 一1 ) j 由性质( 8 ) 知i f ( n ，) i = l l ( c k ) 一f ( 勺) l2 f f ( 勺+ 1 ) 一f ( 勺) i i l ( c 3 ) 一f 滔) f = i t ( c 1 ) j = f l ( a 。) i ，这与性质( 5 ) 产生矛盾所 以f ( 口。) + f ( c ，) 不是标号 当j = t 时，由性质( 6 ) 及( 2 2 ) 知l ( a i ) + 2 ( q ) lz ( b n ) i 一2 1 l ( b 。) i = - i l ( k ) f 则可设z ( 啦) + z h ) = z h ) 或z ( d 2 ) 当l ( a i ) 十( c 0 = l ) 时知 l ( a 1 ) = 0 ，这不可能因为标号( 2 2 ) 中没有0 当f ( 啦) + l ( c t ) = t ( d 2 ) 时知 l ( a i ) + z ( a 。) 一f ( 白一z ) = 一f ( q 1 ) ，则有f ( ) = 一f ( 。) 与性质( 5 ) 产生矛盾 因此l ( a i ) + z ( q ) 不是标号 所以对于任意的1 i r n ，2 js 、f ( 。) + 2 ( 勺) 都不是标号 ( i i i ) 对于任意的a i f ) m ，也p 3 ，我们考虑l ( a 1 ) + f ( 吗) ，其中1si l ( d 3 ) 由性质( 5 ) 1 4 硕士学位论文 m a s t e r st h e s i s 知f ( o i ) + f ( d 3 ) 不是t = p ( 3 ；m ，礼，t ) 4 ) 中点的标号如果f ( 。i ) j t ( b 。) f + i ( c t 1 ) i f ( 口。) l + t ( c t 一1 ) = 1 t ( c 1 ) l + ( 岛一) 2l ( c t 一，) 一l ( c 1 ) = l f ( c t ) i 因此再由性质( 5 ) 知l ( a 1 ) + f 涵) 不是标号 综合上面两种情况知对于任意的l 曼t m ，2 js3 ，f ( o i ) + z ( 出) 都不 是标号 ( i v ) 对于任意的坟只，勺r ，我们考虑f 慨) + f ( 勺) ，其中2 。n ，2 j t ，因为当 = 1 或j = 1 时b l 和勺在同一条路上 当2 jst l 时，由性质( 5 ) 及( 2 2 ) 知 z ( k ) isz ( ) + f ( c j ) jz ( 6 扎) + z ( c t 一1 ) l ( c 2 ) + f ( q 1 ) j 当 k = 3 时得到l2 ( k ) i = 1 i ( c 3 ) l ( c 2 ) l = i i ( c ) 1 = i t ( b 1 ) l ，这与i22 矛盾当 k 4 时，由性质( 5 ) 和( 8 ) 知f ( 6 。) l = l l ( c k ) 一f ( 勺) i l ( c ) f ( 钆一，) i l ( c 4 ) 一f ( c 3 ) i = i f ( c 2 ) i 1 f ( h ) | ，再由性质( 5 ) 及条件i n 知矛盾因此当 2 歹t i 时z ( 瓯) + f ( 勺) 不是标号 当j = t 时，由性质( 5 ) 和( 6 ) 知f ( 6 。) + f ( c ) l ( d 3 ) ，由性质( 5 ) 知 2 ( k ) + l ( d 3 ) 不是标号如果f ( 6 ) l ( o t 一1 ) 同时有l ( b i ) + f ( d 3 ) f ( k ) 4 - l ( c 2 ) + f ( c t 一1 ) = z ( 巩) + 2 i z ( 6 。) 【+ f ( c t 一1 ) l ( c t 一1 ) 十f f ( “) f l ( c t 一1 ) + f f ( 6 1 ) i = l ( c t 一1 ) + i l ( c 1 ) l2f ( c f 一1 ) 一l ( c 1 ) = j f ( c c ) 1 再由性质( 5 ) 知f ( 玩) + l ( a 3 ) 不是标号 标号 综合上面两种情况知对于任意的2 i 扎，2 j 3 ，f ( 玩) + 2 ( 吗) 都不是 ( v i ) 对于任意的q p t ，d j p 3 ，我们考虑f ( 岛) + t ( d j ) ，其中2 i t ，2 j 3 ，因为当i = 1 或j = 1 时c i 和吗在同一条路上 首先考虑f 慨) + f ( d 2 ) 当i f ( c t 一1 ) + z ( c t 一2 ) = z ( d 3 ) 由性质( 5 ) 知z h ) + z ( 矗2 ) 不是标号 对于f h ) + t ( d 3 ) 当i t 时，由性质( 4 ) 知f ( c ：) + l ( d 3 ) l ( d 3 ) ，由 性质( 5 ) 知l ( q ) + l ( d 3 ) 不是标号当i = t 时，由( 2 2 ) 知f ( c ) + z ( d 3 ) = 1 6 硕士学位论文 m a s t e r st h e s i s l ( c 1 ) 一f ( q 一1 ) + f b 一1 ) + l ( e t 一2 ) = 1 ( c 1 ) + l ( e t 一2 ) ，由情形2 中的( i i i ) 知他不是 标号 综合上面两种情况知对于任意的2 i t ，2 j 3 ，l ( c i ) + t ( d j ) 都不 是标号 结合( i ) 一( v i ) 知情形3 成立 由情形1 3 知t = p ( 3 ；m ，n ，) ( 其中f 4 ) 中所有不相邻两点的标号 和不是标号综合以上证明知所有的g r i p - l i k et r e et = p ( 3 ；m ，佗) 是f e g r a p h s ( t 4 ) 1 7 硕士学位论文 m a s t e r st h e s i s 3 1 问题的提出 第三章奇圈 问题3 1 1 在文献御中许宝根提出是不是所有的奇圈都是f 一g r a p h s 这一问题 l s m e l n i k o v 和a 矿p y a t k i n 在珂中证明了除a 的所有2 一正 则图都是整数和图，此结论是对该问题的一个肯定的回答下面我们用另外一 种方法证明所有的奇圈都是整数和图 32 所有的奇圈都是，一g r a p h 定理3 2 1 如果扎奇数，则圈g 是，一g r a p h 证明：我们首先考虑礼21 1 的情形把& 记为暖= ( a t ，a ：，a ，) 其中礼为奇数对g 的标号如下： l ( a 1 ) = a ，l ( a 2 ) = b ，l ( a 1 ) = f ( o ；一2 ) 一i ( a i 一1 ) ( i = 3 ，4 ，n 一4 ) ， z ( 。一3 ) = l ( a 1 ) 一z ( a 。一4 ) ，l ( a 。2 ) = - - l ( a 2 ) 一l ( a 。一3 ) ，( 3 1 ) l ( a n 一1 ) = l ( a 1 ) + l ( a 2 ) = a + b ，f ( ) = - i ( a 2 ) = 一b ， 其中b 2 a 0 ，b 3 a 且a ，b z 则我们得到序列s = ( z ( 。1 ) 、l ( a 2 ) ，l ( a 。) ) 有如下性质： ( 9 ) 对于3 isn 一4 ，i 为奇数时，l ( a 1 ) 0 ，i 为偶数时，l ( a 。) f l ( a 。一4 ) j 对于f ( 。z ) ，由( 3 1 ) 及性质( 9 ) 知f ( 。一2 ) = - t ( a 2 ) 一l ( a 。一s ) ，则有 i f ( n n - - 2 ) l i l ( a 。一3 ) f - 所以i f ( 。一。) l | f ( 。一3 ) l i t ( a n 一。) | 对于f ( 。一1 ) ，由( 3 1 ) 知f ( n 。一1 ) = l ( a 1 ) + l ( a 2 ) = a + b b = l ( a 2 ) a = z ( 。1 ) 因此有l ( a 。一1 ) l ( a 2 ) l ( a 1 ) 0 对于l ( a 3 ) ，由( 3 1 ) 知 f ( 船) i = i l ( a 1 ) 一f ( 口2 ) j = b a 2 a a = l ( a 1 ) 另 外有i ( 0 3 ) l = 1 f ( n - ) 一f ( 0 2 ) 1 = b - o l f ( 0 3 ) l i f ( 凸) l _ 对于z ( 口4 ) ，由( 3 1 ) 知l ( a 4 ) = l ( a 2 ) 一l ( a 3 ) = 2 b a = b + b 一。 b + a = l ( a n - 1 ) 因此有l f ( 口4 ) l j l ( a