（基础数学专业论文）图论中和图标号问题的研究.pdf

大连理工大学硬士学位论文 摘要 图论是数学的一个分支，特别是离散数学的个重要分支，它在物理、化学、天文、 地理、生物学，尤其是计算机科学中有非常广泛的应用 本文主要研究图的标号问题，图的标号问题起始于1 9 6 6 年a r _ o s a 的著名的优美树 猜想一个图的顶点标号是图的顶点集到整数集的映射而根据对映射的不同的要求， 产生了各种各样的图的标号问题1 9 8 8 年，f h a r a r y 给出( 整) 和图的标号；1 9 9 0 年， b o l l a n d ，l a s k a r ，y a r n e r 和d o m k e 把和图推广到模和图2 0 0 0 年，s o n n t a g 和t e i c h e r t 把 ( 整) 和图的概念推广到超图上 和图标号在射电天文学及计算机网络理论中有着广泛的应用本文研究了三类标号： ( 整) 和图标号、模和图标号、( 整) 和超图标号分别解决了三类标号中的一些问题和猜 想主要工作概括如下： 给出完全三部图k 1 l ，r 3 的( 整) 和数、完全三部图凰 ，r 2 ( 整) 和数的个 上下界；并证明了扇图r 及任意个扇图在中心处相交构成的图是整和图，同时荷兰风车 工k 也是和图、整和图、模和图c h e n n 猜想树是整和图，本文证明了花树是整和图；用 粘合法推广了一类整和图( 任意个整和图和三叉树的沾合) ；给出单位图( 一( g ) = 1 ) 和 星图的并，任意星图的并是整和图 s u t t o n ，m i l l e r ，r y a n 和s l a m i n 2 4 中提出了两个问题：扇图( 矗) 和砺，。的模和数 本文证明了扇图( f n ) 不是模和图，并给出当n 偶数时，p ( 晶) = 2 1p ( 。) = n s o m a t a g 和t e i c h e n m 猜想；当d n 一2 时，( ( 帮) = 口( 盘) 本文| 证明了当n22 d + 1 时，e ( 剃) = a ( j 野) 当d 4 时，给出了d 正则超圈是超整和图把模和图推广到超 图上去，并证明了当d 4 时，击正则超树，正正则超圈是超模和图给出完全击正 则超图( 彳宰) ，当d = q n 一1 ，j 纡是模和超图，当n 2 4 + d 不是模和超图 关键词：( 整) 和图；模和图；( 整) 和超图；模和超圈 张明：图论中和图标号问题的研究 r e s e a r c ho ns u mg r a p hl a b e l i n gp r o b l e m si n g r a p ht h e o r y a b s t r a c t g r a p ht h e o r yi sab r a n c ho fm a t h e m a t i c s ，e s p e c i a l l ya ni m p o r t a n tb r a n c ho fd i s c r e t em a t h e m a t i c s i th a sb e e na p p l i e di nm a n yd i f f e r e n tf i e l d si nt h em o d e r nw o r l d ，s u c ha sp h y s i c e s ， c h e m i s t r y , a s t r o n o m y , g e o g r a p h y , b i o l o g y , a sw e l l i nc o m p u t e rs c i e n c ea n de n g i n e e r i n g t h i st h e s i sm a i n l yr e s e a r c h e so ng r a p hl a b e l i n g g r a p hl a b e l i n gt r a c e si t so r i g i nt ot h e f a l o l l sc o n j e c t u r et h a ta l lt r e e sa r eg r c e f u lp r e s e n t e db ya r o s ai n1 9 6 6 v e r t e xl a b e l i n gi sa m a p p i n gt h a tm a p s t h ev e r t e xs e ti n t oi n t e g e rs e t a c c o r d i n gt ot h ed i f f e r e n tr e q u i r e m e n tf o rt h e m a p p i n g ，m a n yv a r i a t i o n so fg r a p hl a b e l i n gh a v e b e e ne v o l v e d i n1 9 8 8 ，f h a r a x yi n t r o d u c e d t h en o t i o no fa ( i n t e g r a l ) s u l 2 1g r a p h s u mg r a p hw a sg e n e r a l i e dt or o o ds u mg r a p hb yb o l i a n d ， l a s k a r ，y u r n e ra n dd o m k ei n1 9 9 0 t h ec o n c e p t so fs u ng r a p ha n dl u t e g r a is u i ng r a p hh a v e b e e ne x t e n d e dt oh y p e r g r a p h sb ys o n n t a ga n dt e i c h e r ti n2 0 0 0 s u mg r a p hl a b e l i n g ss e r v e sa su s e f u lm o d e l sf o rab r o a dr a n g eo fa p p l i c a t i o n ss u c ha s a s t r o n o m ya n dc o m m u n i c a t i o nn e t w o r k s t h r e ec l a s s e so fg r a p hl a b e l i n g ：( i n t e g r a l ) s l n ng r a p h l a b e l i n g ，r o o ds u mg r a p hl a b e l i n g ，( i n t e g r a l ) s l l u 2h y p e r g r a p hl a b e l i n ga r er e s e a r c h e d ，s o m e p r o b l e m sa n dc o n j e c t u r e sh a v eb e e ns o l v e dr e s p e c t i v e l y t h e 城r e s u l t so b t a i n e di nt h i s t h e s i sc a nb es u m m a r i z e da sf o i t o w s ： t h ea u t h o rg i v e s 叮( k 1 1 ) = ( ( k 1 。l ，r ) = rr 3a n dg i v e st h eu p p e r ( 1 0 w e r ) b o u n d o f ( ( ) a k l r 2 ；p r o v e sd u t c h m - w i n dm i l l ，f a na n df l o w e rt r e ea r ei n t e g r a ls u mg r a p h s ； c o n s t r u c t sai n t e g r a ls u mg r a p hb yi d e n t i f y i n gt h r e e - p a t ht r e ew i t hac o n n e c t e di n t e g r a ls u m g r a p h ；p r o v e s t h e u n i o no f u n i t g r a p h a n ds t a ra n d t h e u n i o n o f a n ys t a r s a r e i n t e g r a ls u m g r a p h - t h ea u t h o rp r o v e st h a tf a n ( 晶) i sn o tar o o ds u mg r a p ha n dg i v et h er o o ds u mn u m b e ro f 最mi 8e v e n ) ；g i v e sau p p e rb o u n do ft h er o o ds u l nn u m b e ro fs y m m e t r i cc o m p l e t eg r a p h ， t h ea u t h o rp r o v e s 盯( 。；昭) = e ( 彳) = d ( n d ) + 1 f o rn 2 d 十1 1 f o rd 4 w e p r o v e t h a t e v e r yd - u n i f o r mh y p e r c y c l e 矽i sa ni n t e g r a ls l n nh y p e r g r a p h ；w es h o wt h a tf o rd2 3d - u n i f o r m h y p e r t r e ea n dd - u n i f o r mh y p e r c y c l ea r er o o ds l u nb y p e r g r a p h s ；w ep r o v et h a td - u n i f o r mc o m p l e t e h y p e r g r a p h sa r em o ds u mh y p e r g r a p h sw h e nd = n n 一1 、d - u n l f o r mc o m p l e t eh y p e r g r a p h s a r e n o t m o ds u mh y p e r g r a p h s w h e n n 2 “+ d k e y w o r d s ：( i n t e g e r ) s u mg r a p h ；m a ds u mg r a p h ；( i n t e g r a l ) s u mh y p e r g r a p h ；m o d s u m h y p e r g r a p h i i 独创性说明 作者郑重声呱本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名：逮垒竺二_ 一日期：之兰：尘塞 大连理工大学学位论文版权使用授权书 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解呔连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印，缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名 旅娩 苷啦 趔年! 目2 日 大连理工大学硕士学位论文 l 绪论 1 1 引言 1 7 3 6 年是图论的历史元年，这一年欧拉( e u l e r ) 研究了著名的柯尼斯堡七桥问题，发 表了囹论的首篇论文，开创了图论科学的研究1 9 3 6 年，匈牙利著名的图论学家k o n i g 发表了有限图与无限图理论，这是图论的第一部专著，它总结了图论二百年的主要 成果，是图论的重要里程碑此后，图论开始飞速发展起来，成长为数学科学中一门独立 的学科它的分支很多，例如，算法图论、极值图论、网络图论、代数图论、随机图论、 模糊图论、超图论等由于现代科技尤其是大型计算机的迅速发展，使图论大有用武之 地，无论是数学、物理、化学、天文、地理、生物等基础科学，还是信息、交通、战争、 经济乃至社会科学的众多问题，都可以应用图论方法予以解决 图论是离散数学的骨干分支，离散数学则是计算机科学技术与网络信息科学的思想 基础多年来，为了实现高速计算的目的。数学促进了计算机科学的形成与发展例如图 灵机的数学理论为计算机的诞生打下了基础；另一方面，随着计算机科学在社会发展中 作用的日益提升，它又反过来促进数学的发展例如，1 9 7 6 年，伊利诺大学的a p p l e 和 h a k e n 用计算机证明了四色猜想成立1 9 9 3 年罗彻斯特理工学院的s p r a d z i s z o w s k l 和 澳大利亚国立大学的b d m c k a y 用计算机求得r a m s e y 数r ( 4 ，5 ) = 2 5 图论最吸引人的特色是它蕴涵着大量强有力的思想、漂亮的图形和巧妙的论证，即 使是非常困难的尚未解决的问题，它的表述也可能是平易近人的现实生活中处处可以 发现图论的难题，图论是最接近百姓生活、最容易阐述的一门数学分支，具有实质性的 难度又有简朴的外表是很多图论问题的特点之一，使得每个搞图论的人在图论问题面前 都必须谨慎严肃她思考，它的证明往往需要极其繁琐的细节。 图论与数学的其它分支不同，它不象数论、拓扑等学科那样有一套完整的理论体系 和解决问题的系统方法图论所涉及的问题比较广泛，而解决问题的方法千变万化，非 常灵活，常常一种问题一种解决方法，而这些方法之间又豪无联系因此，解决图论中 的恳题不仅仅需要知识，而且还需要智慧和灵活深入的思考 从2 0 世纪6 0 年代之后，图论的算法受到了更多的重视算法的有效性一直困惑着 我们例如我们建立了两个顶点之间最短路径的d i j k s t r a 有效算法，却建立不起来求两 个顶点问最长轨道的有效算法；也没有有效算法判别图的顶点是否全部处于一个圈上， 没有有效算法确定能否用三种颜色对地图正常着色。在网络理论中，已经有有效算法， 把商品在铁路上由产地最快的运往销地，但对两个工厂的两种商品，分别运往各自的销 地时，建立不了安排运输方案的有效算法，使的两个销地的嚣求同时得以满足，等等 张明：图论中和图标号问题的研究 至今已积累了数以千计的实际问题，其数学模型是图论问题，但这些问题皆未建立有效 算法2 0 世纪8 0 年代，e d m o n d s ，c o o k 和k a r p 等发现，这些难题有一个值得注意的奇 特性质，如果这些问题中有某个问题不存在有效算法，贝l 不能指望这批问题中的任何一 个存在有效算法了这批问题组成的集合记成n p c ，或称n p 完全问题数学与计算机 科学的最大挑战之一就是回答n p c 问题是否真的不存在有效算法。 1 2 图论的基本概念 一个图是由非空点集v = v c v ) 和y 中元素的无序对的个集合e = e ( g ) 所构成 的二元组，记为g = ( v c g ) ，e c g ) ) ，简记为g = e ) ，v 中的元素称为顶点或者点，冒 中的元素称为边我们用m ( g ) = i e l 表示图g 中的边数，用n c g ) ) = i v i 表示图的顶点 个数。个图的顶点个数又称图的阶；在不引起混淆的情况下简记为m ，n 对u ，”y ( g ) ， 若“口e c c ) ，则称u 与口邻接，否则称不邻接，记为u 口萑e ( g ) 若边e 1 ，e 2 刀( g ) 有一 个公共顶点，则称e 与9 2 相邻 如果一个图的g 的顶点集v c g ) 与边集e ( g ) 都是有限集，则称该图为有限图，否 则，称为无限图本文仅讨论有限图只有一个顶点所构成的图称为平凡图，其它所有 的图称为非平凡图显然，至少有一个顶点才能称为图所以我们总要求一个图的顶点 集合是非空的 条边的两个端点如果相同，称此边为环，两个点之间多于一条边的，称为多重边 不含环和多重边的图称为简单图，含有多重边图称为多重图设v ( d ) = 伽，也，v ，) 是个非空有限集合，a c o ) = o 。，凸2 ，口口) 是与v c d ) 不相交的有限集合一个有向 图d 是指个有序三元组( d ) ，a ( d ) ，如) ，其中妒d 是关联函数，它使a ( d ) 中的每一 个元素( 称为边或弧) 对应于v ( v ) 中的有序元素( 称为顶点或点) 对( 可以相同) 若 。是一条而u 和, f l 是使得如( 。) = ( u ，”) ( ( ”，u ) ) 的顶点，则称a 从u 指向”；称 t i 是a 的起点，”是。的终点，简记为a = ( u ，n ) 以点”v c g ) 为端点的边数叫做点”的顶点度，记作d g ，无混淆情况下筒记为 d ( ”) 或也顶点度为d 的顶点称为d 度点，零度点称为孤立点，1 度点称为悬挂点，连 接悬挂点的边称为悬挂边用( g ) 和d ( g ) 分别表示图g 的最大和最小顶点度，简记为 和j 若v ( g ) = v l ，啦，) ，称非负整数序列 d ( 1 ) ，d 池) ，d ) ) 为图g 的度 序列 每一对顶点f 研耶有边相连的无向简单图称为完全图，有n 个顶点的无向完全图记作 j 毛图g 称为二部图或者偶图，如果点集y 可以分成两个非空子集五y ，即x u y = v 且 x n y = 0 ，使得e 中每条边的一个端点属于x ，另个端点属于y 二部图g 称为完全 图，若对任意“置”y ，都有“”e 若完全二部囹的两个部分有j 互卜= 5 ，j yj ：t ， 则记作风“当其中的一部分，不妨设x 只含有个点时，我们称为星，记作k 1 “其 中度为t 的点称为星的中心 如果一个图g 中每个顶点的度是某一固定整数k ，则称该图g 是k 正则图在二部 墨g 中，每一部分中的点都有相同豹度，则称该图g 为半正则图 2 大连理工大学硕士学位论文 路r 是指点集为y ( r ) = 叽，啦，”。 ，边集为e ( 晶) = t ”l 睨，一l ”。) 的图， 或称为路( 钆，) ，或咀一路，n 一1 是路的长度起点和终点重合的道路叫圈 长度为的圈称为k - 圈；为偶数，称偶圈；为奇数，称奇圈；3 一圈常称为三角形 n 个顶点的圈记作g g 中点u 与”称为连通的，如果在g 中存在u 一”路若g 中任意两点连通，则g 称为连通图，否则称g 不连通没有圈的图我们称为森林，记作f ；没有圈的连通图称 为树，我们记作t 树中度为1 的顶点称为树的叶子 图日称为g 的子图，如果v ( h ) y ( g ) ，f ( 日) e ( g ) ；若日包含g 的所有的点， 则称日为g 的支撑子图；当日是森林对，我们称为支撑森林；当丑是树时，我们称为 支撑树对集合x y ( g ) ，导出子图 或g p q 是以x 为点集的g 的最大子图 图g 1 = m ，e 1 ) 和g 2 = m ，局) 的并是图g = ( ku ，e lu 岛) ，记作t g 1ug 2 在g 中顶点的连通关系下，可将v ( a ) 划分成有限个等价类，其中每一个等价类构 成的g 的子图称为g 的一个连通分支，g 的连通分支数目记为u ( g ) ，可见g 为连通图 当且仅当u ( g ) = 1 若在图g 中去掉一个点后图的连通分支数增加，则称该点为g 的割 点 设g c 是以v ( g ) 为顶点的图，若g c 中两点在g 。中相邻当且仅当它们在g 中不相 邻，则称g 。为g 的补图 图g 1 与g 2 称为同构的，记作g 1 皇g 2 ，如果存在双射蛋：y ( g 1 ) _ y ( g 2 ) ，是对 任意u ，”v ( a 1 ) ，u ”e ( g ) ，当且仅当西( t ) 壬( ”) e ( g 2 ) ，我们说图g 的一个复制指的 是与图g 同构的图 令v = 矗l ，。2 ， 是一个有限集。关于矿上的一个超图纩= ( k ) ，毋= e l ，e 2 ，玩是y 上的个有限集簇，使得：( 1 ) 噩0 ( i = 1 ，2 ，m ) ；( 2 ) u 罂1 忍= v 在超图超图劈中，y 中的元素t ，2 ，称为顶点，集合置，马，玩成为边简 单图是每条边均含2 个顶点的简单超图；一个多重图是一个每条边不超过2 个顶点的超 图 与图类似，超图纩的顶点数称为。彤的阶，用n ( 矿) 表示边用- 1 ( y f ) 表示此 外，r ( 形) = m 口悖f 称为秩，s ( 澎) - 喇勺畅f 称为下秩；如果r ( 矧= 8 ( x f ) ，则称澎 是一致超图 本文所考虑的图均为无环、无重边的简单有限无向图文中的图论术语和记法主要 参考b o n d y 和m u r t y 的著作g r a p ht h e o r yw i t ha p p l i c a t i o n s l i j 1 3 图的标号问题 1 3 1 和图、整和图标号问题 图的和图和整和图标号问题作为图的标号的种形式，在图论中极其有趣的内容， 有着较好的应用价值和研究前景它的研究始于1 9 8 8 年，h a r a r y 提出了和图和整和图的 3 张明：图论中和图标号问题的研究 而整和图却可以是连通的，而对于一个有m 条边的n 阶图g ，g u m k t 必是和图只需标 定g 的顶点为3 ，1 茎isn ，同时对忱”，e ( a ) 标定对应舸孤立点分+ 即可因此对每 一个图g 都存在最小的菲负整数n 使得g u r k z 为和图，这个数称为和数，记a ) = r 可以类似定义图的整和数e ( g ) ，只需将标号范围规定在整数集上，易知e ( g ) a ( g ) ，显 然一个图g 为( 整) 和图当且仅当口( g ) = o ( e ( g ) = o ) h a r a r y 1 0 提出了许多问题，此后，许多人围绕这几个问题开始对和图和整和图的研 究。 e l l i n g h a m n 证明了h a r a r y 的猜想：对任意树t k t ，a ( t ) = 1 b e r g s t a n de ta 1 3 5 】证明了口( 艮) = 2 n 一3 m i l l e re ta 1 【1 5 】给出了当n 是偶数时口( 1 ) = 等+ 2 ；当n 是大于等于5 奇数时 口( - ) = n m i l l e r ，r y a n ，a n d s m y t h 1 q 得到了完全n 部图且每个部分只有2 个顶点的酒会图岛。的和数，即 o ( 2 。) = 4 n 一5 ；并得到完全n 部图且每个部分只有m 个顶点和数的上下界 s h a r a r y 2 6 1 证明了当n 4 时，瓯和是整和图 c h e n s 】给出了一种构造整和图的方法；沾合法，证明了广义星图( 星图的每一条边 延伸成一条路) 是整和图并且猜想任意树是整和图 w u ，m a o ，和l e l 2 s 给出了m 晶是整和图他们进一步证明了h a r a r y 的猜想当3 ，5 时盯( g ) = e ( 瓯) 是错误的 b x u c s l 给出了下列整和图：三个星图的并、t u 凰。对任意的树t ，m k 3 ，对任 意m 、任意整和树的并 l i a o ，k u o ，和c h a n g 1 4 】证明了所有的毛虫树是整和图，蚀们证明了所有的除q 的所 有圈是整和图 s i n g h 和s a n t h o s h s 6 1 给出了王冠图n 4 的g o 墨是整和图 1 s 2 模和图标号问题 b o l l a n d ，l a s k a r ，y u r n e r 和d o m k e 4 把和图推广到模和图一个图g = ( ke ) 是模和 图，那么存在一个正整数z 和一个关于g 的标号函数， ，g 的顶点从 o ，l 2 ，。一1 ) 取不同的元素，如果u e 当且仅当a ( “) + ( 口) ( m o 出) 属于 o ，l ，2 ，z 一1 ) ，显然所 有的和图是模和图，只要取足够大的模就可以；但是模和图并不都是和图s u t t o ne ta 1 定义了模和数连通图g 的模和数，p ( c ) ，是最少的顶点r k x 使得gur k l 是模和图 显然g 是模和图当且仅当p ( g ) = 0 b o u a n de ta 1 4 给出了工了图是模和图：所有阶大于3 树、g 4 ) 、岛，。、w 4 ； 进一步得到了玛白2 ) 不是模和图，并猜想矸名4 ) 是模和图， s u t t o n ，m i l l e r ，r y a n 和s l a m i n 2 4 否定的b o l l a n de ta 1 的猜想证明了- 4 ) 不 是模和图，同时也证明了当n 3 ，。不是模和图在这篇文章中提出了两个问题：扇 图( f ) 和，。的模和数 g h o s h a l ，l a s k a r ，p i l l o n e ，和f r i c k e 8 】证明了每一个连通图是一个连通模和图的导出子 图和任意一个至少有两个n 一1 度顶点的n 阶图不是模和图 s u t t o n ，m i l l e r 1 证明了当7 2 m 3 时，。不是模和图和p ( ) = ，( 扎4 ) 4 大连理工大学硕士学位论文 s u t t o n ，d r a g a n o v a 和m i l l e r 2 s 给出当n 是大于等于5 的奇数时，p ( - ) = n ；n 是偶 数时，p ( ) = 2 w a l l a c e 证明了当n 是偶数且n 2 m 或者n 是奇数且n 3 m 一3 时，。是模和 图；当3 茎m 茎n 2 m 时，p ( ，。) = m 1 3 3 和超图、整和超图标号问题 s o n n t a g 和2 m c h e r t 3 4 把和图，整和图的概念推广到超图上是自然数集，+ = o ) 令scn + 是有限集，如，n ，。n + 并且1 西咖。对于任给的超图 护= ( k 占) ，我们记：d “。= 吐“。( ? 护) = m i - l e i ：e 毋，d 。= d 。( j 纩) = m o z j e ： e 毋镅。d ，。( s ) = 芎) 称为s 的( d m 机，如。) 一和超图当且仅当v = s 并且 芎= ( b s ：南“。i e i 茎如。，z s ) e 于是，一个超图? 纩= 芎) 当且仅当存在s n + ，如。+ 使得矽同构于 搿氛。凼。( s ) 类似于和图，用t = a ( 并) 代表钟的超和数，也就是最小的数使得彤u ( “1 ，u t ) 是和超图，u 1 ，u t v 是孤立点如果scz ，我们可以用同样的方法定 义整和超图和超整和数“彤) 显然e ( ) 5f ( 纩) s o n n t a g 和t e i c h e r t 3 4 证明了任意超树的超和数是1 在 3 3 】给出了每个d - 正则超图 是整和超图，d23 ；给出竹阶d 正则完全超图的超和数是d 一d ) + 1 ，此处n d + 2 ； 当d = n ，n 一1 时，n 阶出正则完全超图的超整和数是o ；当d n 一2 时，给出了n 阶 击正则完全超图的超整和数的上下界：( d 一1 ) 一d 一1 ) 兰e ( j 绍) d m d ) + 1 他们猜 想：当d n 一2 时，e ( 搿) = f ( 船) t e i c h e r t 给出了在一定的限制下超圈、超轮的超和数是1 _ 同时给出了完全m 一部超 图超和数的上界 1 4 本文的工作 本文主要研究图的三类标号问题：和图和整和图标号，模和图标号，超和图和超整 和图标号分别解决了下列问题： 1 完全三部图k 1 ，1 ，rr 3 的( 整) 和数、完全三郝图k 1 r 2 ( 整) 和数的一个上 下界；并证明了扇图昂及任意个扇图在中心处相交构成的图是整和图，同时荷兰风 车三k 也是和图、整和图，模和图 2 c h e 6 】猜想树是整和图，本文证明了花树是整和图；用沾合法推广了一类整和图( 任 意个整和图和三叉树的沾合) ；给出单位图( a ( g ) = 1 ) 和星图的并，任意星图的并 是整和图 3 s u t t o n ，m i l l e r ，r y a n 和s l a m i n 在幽中提出了两个问题：扇图( 晶) 和瑞，。的模和 数本文给出当n 偶数时，p ( r ) = 2 ；p ( ，。) = n 5 张明，图论中和图标号问题的研究 4 s o n n t a g 和t e i c h e r t 3 3 中猜想：当ds 一2 时，“彳) = a ( 篙? ) 本文证明了当 n 兰2 d + 1 时，( ( 捌) = 盯( 呼) 当d 4 时，给出了d - 正则超圈是超整和图 5 把模和图推广到超图上去，并证明了当d 4 时，d - 正则超树，d - 正则超圈是超模 和图给出完全d _ 正则超图( 删) ，当d = n ，n 一1 ，钾是模和超图，当n 2 4 + d 不 是模和超图 6 大连理工大学硕士学位论文 2 和图、整和图 本章主要给出完全三部图k 1 ，1 ，r 3 的( 整) 和数、完全三部图k i ，vr 2 ( 整) 和 数的个上下界；并证明了扇图晶及任意个扇图在中心处相交构成的图是整和图，同时 荷兰风车五i n 也是和图、整和图证明花树是整和图；用沾合法推广了一类整和图( 任意 一个整和图和三叉树的沾合) ；给出单位图( a ( g ) = 1 ) 和星图的并，任意星图的并是整和 2 1 完全三部圉髓，1 ，、匝 r ， 2 11r i ，l ，的( 整) 和数 在这部分中，我们将要决定a ( 噩，。，) 和“凰，) ，其中r 3 当r = 1 时，我们可以 知道盯( 髓，1 ，) = 2 ，( ( 匝) = 0 我们令m = e ( 噩) ，s = v ( k z ，1 ，ru i n k l ，其中r 3 那 么s 一定存在一个整和标号，对于这个整和标号我们设( 五rz ) 是k i ，v 的三部图 x ：知 ；y ： 讣；z = z l ，砘，御) ，z l z 2 z r ；不妨设z y 因为r 2 3 ，我们 可以看出t o ，vu s ，下面几个引理在证明中将要用到 引理2 1 1 1 ( 1 ) 若jz z 使得z + y = z ，那么v p z 且p 。，z + p 圣z ，y + p 薯z ( 2 ) 若。+ 隹z ，那么v 孑z ，。+ = z ，。+ z 簪z 证明：用反证法证明 ( 1 ) 若3 p ，p z 使得z + p z ，那么y + x + p s ，我们可以看到y + x + p 2 扫+ z ) + p 这样有+ g x u y ，与。十y = z 矛盾，因此z + p 隹z 同理可证y + p 隹z ，妇z ( 2 ) 若jz z ，。+ z z ，那么y + z + z s ，我们可以看到y + z + z = + z ) + & 这样有g + z x u y ，与z + g = z 矛盾，因此z + z 隹z 同理可证y + z 隹z ，vz z 弓i 理2 1 1 2 对vz z ，善+ z 掣，y + 。z 证明：用反证法证明分两种情况： 情况1 ：若引理2 1 1 1 ( 1 ) 满足那么z + z y 下面证明v p z p z 有x + p y ，若 j p z ，使得x + p = 玑那么jq z ，g p g z ，且q + x + p s ，又知q + x s , q + x p ， 从而q + z = y 这与p + 。= y 矛盾故vz z 。+ z y 情况2 若引理2 1 1 1 ( 2 ) 满足若jz z 使得。+ z = y ，那么jp z ，p z ，且 7 张明：图论中和图标号问题的研究 p + 。+ z s ，又知p + 。s , p + z z ，从而p + z = y 与z + z = y 矛盾从而得证对 vz z ，o + z y 由情况1 和情况2 证明了v z e z ，。+ z y 可以类似证明v z z ，y + z 。 定理2 1 1 1e ( 蜀，1 ，) = | c z ( k 1 ，1 ，) = r ，r 3 证明：由引理2 1 1 1 ( 1 ) 和引理2 1 1 2 知：若g + y = z r ，那么有r + 1 个不同的顶点 z + z l o + 恐 o + z r y + 磊 属于s 但不属于x u y u z 若z + y = 毛，且1 r ，那么有r 个不同的顶点 z + z l z + z 2 。 o 十z t i z 十z + l 。 z + 御 y + 并 属于s 但不属于x u y u z 由引理2 1 1 1 ( 2 ) 和引理2 1 ，1 2 知有r 十1 个不同的顶点 z + 乱 o + 砘 - 一 嚣+ z r y + z r ：联 8 大连理工大学硕士学位论文 z = g ) ；m = “1 ，“2 ，。) ；下面几个引理在证明中将要用到 弓鞫至2 1 1 3 1 1 对v z x ，v y y ，。十y 圣x u y 5 i 理2 1 1 4 对v z x ，v y ，z + y z 证明：用反证法 不妨设jz x ，jy y ，使得z + = z ，那么对v p x ，p z ，p + z s ，我们可以 看到p + 。+ y = 函+ 们+ 。，叉由于p + y 只p + y 2 ，从而p + y y ，这与引理2 1 1 2 矛盾所以对vz x ，v y ，$ + y 2 弓l 理2 1 1 5 对vz x ，v 豇y ，+ y m 证明：由引理2 1 1 3 和引理2 1 1 4 得 定理2 1 ，t 2 当r 2 ，2 r 一1 s f ( 蜀 ，) f ( 蜀，) s3 r 一1 证明：由引理2 1 1 5 ，至少有2 r 一1 个不同的顶点 茹1 + 可1 现+ 材2 坼+ 玑 z r + 抛 1 定理