(应用数学专业论文)关于(下)整和图的若干结果.pdf_第1页
(应用数学专业论文)关于(下)整和图的若干结果.pdf_第2页
(应用数学专业论文)关于(下)整和图的若干结果.pdf_第3页
(应用数学专业论文)关于(下)整和图的若干结果.pdf_第4页
(应用数学专业论文)关于(下)整和图的若干结果.pdf_第5页
已阅读5页,还剩43页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他 人已经发表或撰写过的研究成果,也不包含为获得( 注:如没 有其他需要特别声明的,本栏可空) 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名:李嫡赤字 导师签字: 学位论文版权使用授权书 南敝 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定,有权保留 并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本 人授权j 盐可以将学位论文的全部或部分内容编入有关数据库进行检索,可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密 后适用本授权书) 学位论文作者签名:李& 讲 导师签字: 签字日期:2 0 0 7 年年月矽日 ( 习舭 签字日期:2 0 0 7 年争月形日 山东师范大学硕士学位论文 关于( 下) 整和图的若干结果 李婧梓 ( 山东师范大学数学科学学院,济南,山东,2 5 0 0 1 4 ) 中文摘要 本文所用图论基本术语与符号遵循文献f l j 1 9 9 0 年h a r a r y 2 l 提出和图的概念1 9 9 4 年h 吖【3 l 提出整和图的概 念令( z ) 表示正整数( 整数) 集,| i v ( z ) 的非空有限子集s 的( 整) 和图 g + ( s ) 是图碱司,其中一g 当且仅当“+ p s 一个图g 称为( 整) 和 图,若它同构于某个sc ,( z ) 的( 整) 和图我们说s 给出了g 的一个 ( 整) 和标号,并且将顶点与其标号不加区分g 的( 整) 和数一( g ) ( ( ( g ) ) 是 使得g u n ,。是( 整) 和图的非负整数n 的最小值 1 9 9 0 年b o l a n d 等人| 4 l 提出模和图的概念模和图是取s c 1 2 m 一 1 且所有算术运算均取模m ( 2i s i + 1 ) 的和图由此,2 0 0 2 年s u t c o n 等 人1 5 j 提出了模和数的概念一个图g 的模和数p ( g ) 是使得g u n 耳。是模 和图的非负整数n 的最小值 2 0 0 6 年,李敏等人l o l 提出下整和图的概念用吲表示不超过实数z 的最大整数( 称为z 的下整数) ,矿表示正有理数集0 的非空有限子 集s 的下整和图g + ( s ) 是图( s ,e ) ,其中“”e 当且仅当【u + 。j s 一个 图g 称为下整和图,若它同构于某个s c 驴的下整和图我们说s 给出 g 的一个下整和标号,并且顶点与其标号不加区分下整和数一( g ) 是使 得g u n k t 是下整和图的非负整数n 的最小值 从实用的观点看,计算机可将图的( 各种) 和标号作为图的压缩表示, 利用它工作时,不仅可以节省内存,还可以加快某些图算法的运算速度 山东师范大学硬士学位论文 到目前为止,对和图的研究主要集中在两个方面:一方面是图的( 模、 整、下整) 和数与其图参数,图结构方面的联系;另一方面确定一些特 殊图类的( 模,整、下整) 和数迄今为止,已经取得了许多成果,提出 了一些好的方法,给出了一些一般的结论,并将和图的研究推广到了超 图上 在本文的第一章中,我们主要介绍了关于和图的一些概念、术语和 符号以及前人关于和图的一些重要研究结果;在第二章中我们讨论了由 粘合得到的一类图的整和性;第三章中,我们确定了偶圈、气球、轮星, 扇星的下整和数;在第四章中,确定了不交完全二部图,完全三部图的 并的下整和性 在本文中,我们主要得到如下定理: 定理2 。1 设岛是关于功的星和图,户f 4 ,6 ) 是毛虫t 的脊,则( 岛,r 。) w ( 丁,n ) 是关于b 上的一悬挂点的星和图特别地( g 0 ,r o ) w ( t ,n ) 是整和图 定理2 2 令( g ,r ) = ( g 0 ,r 0 ) ,r ) ,其中g 0 是关于r o 的星和图, ( g ,) = ( d ( 儿2 ,m ) ,) 是广义星,其中t 是这些路中最长路的长,m 是这些路中长为i 的条数( 1s i s f ) ,则g 是整和囝 定理3 1 1 3 除a 为下整和图外,偶圈q 。的下整和数为1 定理3 2 - l 当n 4 且n 为偶数时,气球g :是下整和图 定理3 3 4 当n23 ,m 2 时,轮星。是下整和图 定理3 3 6 当m 1 时,扇星晶。是下整和图 定理4 1 3 ,。u 。u u ,。,是下整和图 定理4 2 3 当m ,n ,p ,f 2 时,。,p u 坼,州的下整和数为2 定理4 2 4 当n 4 时,耳l ,。u 坼,“为下整和图 关键词:( 下) 整和图;( 下) 整和数;( 下) 整和标号 分类号;0 1 5 7 5 2 虫变塑堕盔兰堡主堂垡丝塞 s o m er e s u l t so n ( 1 0 、r ) i n t e g r a ls u mg r a p h s “j i 略z i s b a n d 彻gn o r m a ju n i v e 瑙i y j i n 8 n ,s h a l l d o n g 2 5 0 0 1 4 p e o p l e sr e p u b l i co fc h i n 8 a b s t r a c t a l lg r a p l 峙c o n s i d e r e di nt h i sp 印e ra r e f i l l i t e ,s i l l l p l ea i l du n d i r e c t e d i ng e n - e r a l ,w ef o l l o wt h eg r a p h t h e o r e t i c a ln o t a t i o na n dt e r m i n o l o 盯o f 【1 】 h a r a r y l 2 】p r e s e n t e dt h ec o n c 印to fs u mg r a p hi n1 9 9 0 h a r a r y ( 3 1 p 麟e n t e dt h e c o n c e p to fi n t e g r a ls u mg r a p hi n1 9 9 4 l e t ( z ) d e n o t et h es e o 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 mg r a p hg + ( s ) 0 fa1 1 0 啪l l i p f y6 i l i t es l l h s e t sc ( z ) i st h eg r a p h ( s e ) w i t h “u ei fa n do n l yi f t + 口舅ag r a p h gi sb a i dt ob e8 n ( i n t e g r a i ) s u mg r 印hi fi ti s i 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 ho f s o m esc 7 、r ( z ) 酞毫s a yt h a ts 速a n ( i n t e g r a l ) s u ml a b e l l i n go f g ,a n d w ec o n s i d e rav e r t e xa n di t sl a b e l i i n ga st h es 咖e t h e ( i n t e g r a l ) s u mn u m b e r 口( g ) ( ( ( g ) ) i st h es m a l l 髑tn u m b e ro fi s o l a t e dv e r t i c 鼯w h i c hw h e na d d e dt og r 档u l ti na n ( i n t e g r a l ) s u mg r a p h t h e c o n c e p to fm o ds u mg r a p hw 鹅i n t r o d u c e db yb o l a n de t a l | 4 li n1 9 9 0 a m o ds u mg r 印hi sas u mg r a p hw i t hscz m 0 a n da l l8 r i t h m e t i cp e r f o r m e d m o d u l omw h e r em i s i + 1 t h e n ,s u t t o ne t a l l 5 lp r e 钾n t e dt h ec o n c e p to fm o d 8 u m 肌m b e r t h em o ds u mn u m b e r ,( g ) o fgi st h ek 蠲tn u m b e rno fi s o l a t e d v e r t i c 鹤n 噩s u c ht h a tg u n k l i sam o ds u mg r a p h i n2 0 0 6 ,“a n dg a o 柳i n t r o d u c e dt h ec o n c e p to f i o w e r i n t e g r a ls u mg r 印h l e t q d e n o t et 圯靶to fa l lp o s i t i v er 8 t i o n a ln u m b e 墙,t h el o w e ri n t e g r 8 l8 u mg r 8 p h g + ( s ) o fa f i n i t e8 u b tscq + j st h eg r a p h ( 只e ) w i t ht 口ei f8 r l do n l yi f 3 山东师范大学硬士学位论文 b + 叫s ag r a p h g j s8 a i d t ob e8 】o 哪j n t e g r a ls u m 黟a p h j f i t i s j s o n l o r p h i c t o t h e l a w e r i n t e g r 8 ls u mg r 印ho f s o m e s c q 。w bs a y t h a ts i sa l o w e r i n t e g r a l s h m 】8 b e 2 2 i n go f g8 n d 孵蕊i d e f8 豫e x8 n di 拓j 8 b e 】j n g 船h es 8 m e t h e l o w e ri n t e g r a l8 u mm l m b e r 盯( g ) i st h es m a l l 铝tn u l l l _ b e ro fi l a t e dv e r t i c 鹤w h i c h w h e na d d e dt ogr 鹳u l t e di na1 0 w e ri n t e g r a ls u m g r a p h n o map r a c t i c 8 lp o i n to fv i e w ,s u ml a b e l l i n 肛c 强b el l s e d 嬲ac o m p r e 嚣e d r e p r 器e n t a t i o no f8g 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 to n l y f o r 船们n gm e m o r ys p a c eb u ta l s 0f o rs p e e d i n gu ps o m eg r a p ha l g o r i 七h r 璐w h e n a d a p t e dt ow o r kw i t ht h ec o m p r 鹪e dr e p r e 明n t 8 t i o no fi n p u tg r 印l l s n o wt h er e 舱a r c ha i m sa tt w oa s p e c t s 0 n ei st os t u d y 恤er e l a t i o nb e t w e e nt h e ( m o d ,i n t e g r a l ,l o w e ri n t e g r a l ) s u mn u m b e r sa i l do t h e rp a r a m e t e r s ,t h es t r u c t u r 鹊 o ft h eg r a p h t h eo t h e ri sa td e t e r m i n l n gt h es u mm l m b e r ,i n t e g r a ls u m m m l b e r , m o ds u mn u m b e ra n dl o w e ri n c e g r a ls u mn u m b e ro fs o m eg r a p hc l a s s 髑s of a r , s o m ea c h j e v 嘲e n t sh a v 8b e e n9 0 t t o n ,s o m eg o o dm e t 量l d d s8 n dg e n e r 8 lt h e o r e m s h a v eb e e ng o t t o na n de x t e n d e dt oi l y p e r g r a p h s t h e 行r s tc h a p t e ro ft l l i sp 印e rg 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 5 i cc o t 卜 c e p t s ,t e r m i n o l 0 9 0 皓a r ds y m b o l e s ,a n ds o m ei m p o r c a n tc o n c l u s i o n so f 辄m 耵印h w h i c ha r eu s e di nt h j sp a p e r ;i nt h e 辩c o n d c h a p t e rw ed i s c u 踞af a m i l yo fi n t e g r a l s u l l lg r a p h sf j o l nj d e l l t 语c a t i o l l ;i i lt h et l l i r dd l a p t e rw ed e t e r m i n et h el o w e ri n t e 。 g r a ls u mn u 埘b e r so fe v e nc y d 签,b a l l o o n ,w h e e l ( ) 一f a p ha n df a n “) g r a p h ;j n t h ef o u r t hc h a p t e r ,w ed i s c u s st h el o w e ri n t e g r a ls u mn u m b e r so fd i s j o i n tu n i o no f c o m p l e t eb i p a r t i t eg r a p h s8 i l dc o m p k t et r i p a r t i eg r 印1 1 8 i nt h i sp a p e rw eo b t a i nt h ef o l l o i n gt h e o r e r r 峙: t h e o r e m2 1l e tg oi sa9 ) 一s u mg r a p hw i t hr 铝p e c tt or 0 ,p ( d ,6 ) i sas p i n e o f ac a t e r p i l l 8 rr ,t h e n ( ( 而,r o ) 阳( 正o ) i sa9 ) s u mg r a 曲w i t hr 酷p e c tt oal e a f o f6 p a r t i c u l a r l y ,( ( 珀,r o ) 闻( 正n ) i 8 蛐i n t e g r a ls u mg r a p h 4 山东师范大学硕士学位论文 t h e o r e m2 2 l e t ( g ,r ) = ( g o ,r 0 ) ( ,r ) a n dg oi sa ( ) 一s u mg r a p h w i t h r e s p e c cc or 0 ,( g ,r ) = ( g l ,犯2 ,佗1 ) ,r ) i sa g e n e r a l i z e ds t a r ,w h e r e 啦i st h e n u m b e ro ft h ep a t 王l sw i t hl e n g t hta n dti 8t h el a r g e s tt8 u c ht h a tm o ,t h e ng i sa ni n c e g r a l8 u m g r a p h t h e o r e m3 1 3 e x c 印t 戗w h i c l li 8al d w 盯i n t e g r a ls u mg r a p h ,t h el o w e i n t e g r “s u mn u m b e ro fe v e nc y c kg ni 81 t h e o r e m3 2 1b a l l o o ng 2i sal o w e ri n t e g r a ls u mg r a p hf o r “ln 4a n d n i se v e n t h e o r e m3 3 4 mi 8a l d w e ri n t e g r a l8 u mg r a p hf o ra i ln 3 ,m 2 t h e o r e m3 3 6r m i sa l o w e r i n t e g r a ls u mg r 印h f o ra l l m 1 t h e o r e m4 1 3 k n h m l u j 厶2 m 2 u u 珞,t ,i ,i sal o w e ri n t e g r a l8 u m g r a p h t h e o r e m4 2 3t h el o w e ri n t e g r a ls u mn u m b e ro f n p u 坼,1i 82f o a 儿,n ,n ,p ,r ,s ,f 22 t h e o r e m4 2 4 l ,m ,n u 珥 li sa l o w e r i n t e g r a 王s u mg r a p h f o ra i i t l 2 4 k e yw b r d s :( 1 0 w e r ) i n t e g r a ls u mg r a p h ;( 1 0 w e r ) i n t e g r a ls u mn u m b e “( 王0 w e r ) j n t e g r a js u ml a b e l l i n g c l a s s 湎c a t i o n :0 1 5 7 5 5 山东师范k 学硕士学位论文 第一章预备知识 1 9 9 0 年h a r a r y 【2 】提出和图的概念1 9 9 4 年h a r a r y 【3 1 提出整和图的概 念令( z ) 表示正整数( 整数) 集,( z ) 的非空有限子集s 的( 整) 和图 g + ( s ) 是图( s ,e ) ,其中w e 当且仅当u + s 一个图g 称为( 整) 和 图,若它同构于某个sc ( z ) 的( 整) 和图我们说s 给出了g 的一个 ( 整) 和标号,并且将顶点与其标号不加区分g 的( 整) 和数一( g ) ( ( ( g ) ) 是使得g u n 坼是( 整) 和图的非负整数n 的最小值 1 9 9 0 年b o l a i l d 等人提出模和图的概念模和图是取s c 1 ,2 ,m 1 ) 且所有算术运算均取模m ( 俐+ 1 ) 的和图由此,2 0 0 2 年s u t t o n 等 人f 5 j 提出了模和数的概念一个图g 的模和数p ( g ) 是使得g u n ,是模 和图的非负整数n 的最小值 2 0 0 3 年m i l l e r 等人提出排斥图的概念图g u n k ,的和标号s 称为 排斥的,若对每条边u n e ( g ) ,u + ”趴y ( g ) 图g 的排斥和数e ( g ) 是 使得g u ”耳- 有排斥和标号的非负整数n 的最小值 2 0 0 6 年,李敏等人l q 提出下整和图的概念用h 表示不超过实数z 的最大整数( 称为z 的下整数,驴表示正有理数集q 的非空有限子 集s 的下整和图g + ( s ) 是图( s ,e ) ,其中u ”e 当且仅当h + v jes 一个 图g 称为下整和图,若它同构于某个s c 驴的下整和图我们说s 给出 g - 的一个下整和标号,并且顶点与其标号不加区分下整和数一( g ) 是使 得g u n 耳- 是下整和图的非负整数n 的最小值 2 0 0 7 年窦文卿等人【8 】提出模整和图的概念模整和图是取sc o ,l ,2 , ,m 一1 ) 且所有算术运算均取模m ( 吲) 的和图个图g 的模整和 数妒( g ) 是使得g u n 风是模整和图的非负整数n 的最小值 不难看出,对于任意图g ,有口( g ) s 口( g ) ,( ( g ) a ( g ) ,妒( g ) p ( g ) s 6 山东师范大学硬士学位论文 寸( g ) ,( g ) sd ( g ) 从实用的角度来看,各种和图标号都可被计算机用作图的压缩表示 当利用它们来工作时,数据压缩不仅可以节省内存,还可以加快某些图 算法的运算速度 1 9 9 1 年,h a r a r y 、h e n t z e l 和j a c o b s f 9 f 定义了实和图的概念实和图取 s 为正实数集的非空有限子集他们证明每一个实和图是和图 1 9 9 2 年,b e r g s t r “d 等人【1 0 j 提出积图的概念令l 表示不包括1 的 正整数集,l 的非空有限子集s 的积图g ( s ) 是图( s ,e ) ,其中u ”e 当且仅当“。s 一个图g 称为积图,若它同构于某个sc l 的积 图 f 1 0 j 中证明每一个积图是和图,每一个和图是积图 和图的概念已经推广到了超图上【u - m ,使得和图理论丰富化、深刻 化 s o n n t a g 和t e i c h e r t i l 】证明了某些条件下的超树的和数为1 这两位 作者还证明了一定限制下的超树是整和图,同时也给出了部分完全超图 的整和数【1 2 】 、 目前对和图的研究主要集中在两个方面;一方面研究图的( 整,模, 摸整下整、排斥) 和数与其图参数图结构的联系;另一方面确定一些 特殊图类的和数、整和效,模和数模整和数。下整和数及排斥和数经 过许多人的研究,目前已确定一些常见图类,如完全图编完全二分图 _ r 一圈g ,n + 1 个顶点的轮、n + 1 个顶点的扇r ,酒会图胁。 等图的( 整、模、模整、下整、徘斥) 和数这些结果可参见f 1 3 j f 4 4 j ,其 中与本文密切相关的有: d 3 j f 】研中证明完全二部图托,( 2s ,一) 的和数为碍+ 照萼二丑1 ,其 中p = f 、乌+ 一 1 李敏1 1 q 证明了完全二部图以,是下整和图,完全 三部图t ,。,口是下整和图,f m 。( m ,n ,口2 ) 的下整和数为2 s cl i a w 等人f 1 1 证明了当n 4 时,圈g 为整和图j b o l d 等 人i 4 j 证明了n 3 阶的树、n 4 阶的圈g 及某些完全二部图是模和图 7 山东师范大学硕士学位论文 s u t t o n m i l j e r 确定了轮( n 5 ) 的和数,当n 为奇数时为n ,n 为偶数 时为+ 2 s h a r a _ r y 1 。证明轮眠( n 4 ) 的整和数为o ,n 一3 时为5 窦 文卿等人【2 0 1 证明扇晶如25 ) 的和数,当n 为偶数时为3 ,n 为奇数时为 4 c h e n f 2 l j 提出了一种得到新的连通整和图的方法一粘合法,并用这 种方法证明了叉点距离至少为4 的树及广义星均是整和图,还猜测树都 是整和图魏建新改进了这个结果,证明了叉点至少为2 的树是整和 图,并由此证得任何一棵树的绍分图都是整和图 8 山东师范大学硬士学位论文 第二章由粘合得到的一类整和图 令岛g 2 是两个图,n 是g t 中的一个固定顶点,称为g 。的根“= l ,2 ) , 令( g 。r ) ;( g l ,r 1 ) ( g 2 ,如) 表示根为r 的图e 它是由g 】、g 2 粘合r , r 2 为一个点,、得到的显然y ( g ) = ( g 1 ) 一f r i ,) u ( y ( 晚) 一亿 ) u r , e ( g ) = e ( g 1 ) ue ( g 2 ) ,且粘合运算是可交换、可结合的 广义星( g ,r ) 是将若干条长度都大于。的路的各一个端点粘合为一点 r 得到的图,记( g ,r ) = ( g ( n l ,m ) ,r ) ,其中n 。是这些路中长为i 的条 数,是这些路中最长路的长。 设g = ( 旷e ) 是图,z 矿单射l p :y z 称为g 关于z 的星和标号, 若g 兰g + ( 9 ( v ) ) ,且任意v 一 z ) 和最小标号点玑满足妒( z ) i 妒( u ) o 9 ( ”) 此时称g 是关于z 的星和图显然星和图是特殊的整和图 去掉1 度点( 叫悬挂点) 后成为路的图称为毛虫,该路叫毛虫的脊, 由f i7 j 我们不难归纳地证观: 定理2 1 设g 。是关于柏的星和图,p ( 玛6 ) 是毛虫丁的脊,则( g 0 ,r o ) w ( 了,n ) 是关于6 上的一悬挂点的星和图特别地( g 旷o ) w 。) 是整和图 本章主要研究星和图粘合广义星所得图的整和性 命题2 ,1 设筘是图g 关于z 的一组星和标号,则任意u v ( g ) 满足 妒( u ) 一9 ( z ) ,士詹妒( z ) ( 七= 2 ,3 。) 命题2 2 星和图一定不含与其它顶点都邻接的顶点( 叫饱和点) 证明因为。不在任意一组星和标号中,由【2 l ,事实3 l 知结论成立 引理2 1 【1 7 2 z j 设咖是关于r o 的星和图g o 的一组星和标号,星托。= ( 工o ,z 1 ,z w ) , z o z l :i = l ,2 ,一,”) ) ,则 9 山东师范大学硬士学位论文 州。) ; 啪。九“以, li 如( 和) 一蜘( 计,“一4 0 = i ,2 ,。一,n ) ( 其中是咖中标号最小的点) 是( g l ,r 1 ) = ( 岛,r 0 ) 阏( 耳- 。z o ) 关于z 。 的一组星和标号 注2 1 显然r l 是| p ,的最小标号点在引理2 2 、23 中所有与引理2 1 中相同的符号,意义也相同 引理2 。2 设尼= n o n 。2 是条路,则( e z ) = ( g i ,r i ) 僻,幻) 存在组 星和标号 证明由引理2 1 , ( 一,n ) = ( g o ,r o ) p q ( ( z ”一,z n ,d 1 ) , o o 政,8 0 n l : = 1 ,2 ,n ) ) ,n o ) 有关于a - 的星和标号矗再由引理2 1 ,令 妒( 。) ; 妒:( u ) ,u y ( ) , 【妒:( r 1 ) 一妒:( d 1 ) ,u = 0 2 则一妒为( g ,z ) 关于n 2 的一组星和标号, 引理2 3 设p 3 = n n 2 n 3 是条路,则( g ,z ) = ( g l ,r 1 ) ( 尸3 :n 0 ) 存在一 组整和标号忆使任意“ey ( g ) 满足妒( u ) 一妒( z ) ,士2 妒( 。) ,且,o 证明令f ( 0 1 ) = p 1 ( y ) 一( t l + 3 ) 妒i ( r 1 ) ,妒( 8 2 ) = ( n + 2 ) 妒l ( r 1 ) ,妒( n 3 ) = 妒1 ( 可) 一 ( n + 2 ) 妒1 ( r 1 ) ,扩充妒l 为妒对任意y ( 岛) 一p l ,计有 # ( 口2 ) 妒( ) 妒( u ) 9 ( p ) p ( z i ) 妒( z 2 ) 妒( z n ) 妒( 口1 ) + 轳( n ) = 妒1 0 ) 一( n 十2 ) 妒l ( 1 ) = 妒( 0 3 ) , 因此z 0 1 n l 2 e ( g + ( 妒) ) ,而l ( 1 3 ,n 1 口掣f ( g + ( 妒) ) ( 2 ) 对 妒( 0 2 ) + l p ( 0 3 ) = 妒l ( 可) = 妒( 妒) ,贝g0 2 n 3 e ( g + ( 妒) ) ; 任取t y ( g 1 ) 一 z ) ,妒( d 2 ) + 妒( t ) s 妒( 口2 ) + 泸( 矗。) = i p l ( ) + 2 妒l ( r 1 ) 妒l ( ”) 一,l 妒l ( r 1 ) = 妒l ( z 。) , 且若( 0 3 ) + 妒( u ) = 妒( 口1 ) , 则妒( u ) = 一妒l ( r 1 ) ,矛盾, 则幻“譬e ( g + ( 妒) ) 至此已证明p 是g 的一组整和标号显然任取u y ( g - ) 有l p ( u ) 一妒( z ) ,士2 妒( z ) 引理2 4 设娜是关于r o 的星和图g 0 的一组星和标号,马= 印n - n 2 n 3 是条路,则( g ,功一( g o ,r o ) 嘲( b ,如) 存在一组整和标号n 使任意t i y ( g ) 山东师范大学硬士学位论文 满足p ( u ) 一妒( ) ,士2 妒( z ) ,且妒o , 证明由引理2 1 ,妒( “) = 一伽( u ) “y ( 岛) ) ,p ( d 1 ) = 妒( y ) 一| p ( z ) 是( g ,z ) = ( g 0 ,r 0 ) w ( 印n 。,d 0 ) 关于n 1 的一组星和标号,显然妒( z ) 最小 再由引理2 1 ,扩充妒( 0 2 ) = 2 妒( z ) 一妒( p ) ,则一妒为( ,z ) = ( d ,n 1 ) ( o n 2 。1 ) 关于n 2 的一组星和标号,显然一妒( 0 1 ) 最小 再由引理2 ,l ,扩充p 她) = 2 妒( y ) 一2 妒( 甸,则p 为( ,眈) w 池吣,衄) 的一 组星和标号,显然妒合于要求 引理2 5 口i j 令( g l ,r 1 ) = n o d l ( 4 t l 6 ) 是条路且根r l = 8 i 。2 l ,( g 2 ,r 2 ) 是根为r :的无饱和点的图,且存在g z 的一组整和标号咖,满足对任意 z 矿( 岛) ,有妒( z ) 一妒( r 2 ) ,士枷h ) ,则存在( g ,r ) = ( 瞰r 1 ) ( 岛,r 2 ) 的一组 整和标号满足对任意:;,( q 有铲一以r ) 2 妒( r ) ,且p o 引理2 6 圳令( q q ) = 如n l ,口。( n 4 ) 是条路且根n = n o ,( 国,力) 是根 为t 2 的无饱和点的图,且存在g 2 的一组整和标号咖,满足对任意zev ( g :) , 有妒( z ) 一妒( r 2 ) 士2 妒( r 2 ) ,则存在( g ,r ) = ( g 1 r 1 ) ( g 2 ,r 2 ) 的一组整和标号 仍满足对任意z v ( g ) 有l p ( 。) 一妒( r ) ,士2 妒( r ) 。且妒o , 定理2 2 令( g ,r ) = ( g n 相) ( ,r7 ) ,其中g 0 是关于的星和图, ( d ,r ) = ( d ( n 2 ,m ) ,r ) 是广义星,则g 是整和图 证明( 1 ) 当n 2 o 时, 1 ) 若n z 、n 3 同为奇数, 则令( g j ,r j ) = ( g o 。r o ) ( h ,z o ) w ( p 5 。n 2 ) ( 局k ) w ( 只k ) ( p 6 ,岛) ( r ,c 3 ) ,其中共粘了( n 2 一1 ) 2 条只,( n 3 1 ) 2 条p 6 ; 2 ) 若啦,珊同为偶数, 则令( g l ,n ) = ( c 南,r 0 ) ( 所。,z o ) ( 只,6 2 ) w ( 只,6 2 ) w ( r ,c 3 ) w ( r c 3 ) ,其中共粘了t 1 2 2 条r ,n 3 2 条r ; 3 ) 著啦为奇数、恕为偶数, 则令( g l ,r i ) = ( ( 玷,r 0 ) h ( j m ,$ o ) w ( b ,d 0 ) d 日( 只,6 2 ) w ( 只,b ) w 山东师范大学硕士学位论文 ( 局,c 3 ) 州闪( r 心) ,其中共粘了( n 2 一1 ) 2 条只,他2 条r ; 4 ) 若n 2 为偶数、勘为奇数, 则令( g l ,r 1 ) = ( 6 b ,r o ) w ( 凰,。,劫) 喇( 恳,印) 嘲( 尼,k ) ( 只,c 2 ) w w ( 只,c 2 ) 嘲( 岛,d 3 ) w ( 岛,d 3 ) ,其中共粘了n 2 2 1 条r ,( n 3 1 ) 2 条r ( 2 ) 当n 2 = o 时, 1 ) 若n 。为偶数, 则令( g l 川) = ( g o r 0 ) w ( 硒。,z o ) d 寸慨,d 3 ) w w 涵,哪) ,其中共粘了 n 3 2 条p 6 ; 2 ) 若n 3 为奇数, 当n 121 时,则令( g l ,r 1 ) = ( 岛,r o ) 闪( 硒m 跏) w ( 忍o o ) ,b ) w ( r ,6 3 ) ,其中共粘了( n 3 1 ) 2 条r ; 当n l = o 时,则令( g l ,r 1 ) = ( 岛r 0 ) w ( 岛。o ) ( r ,6 3 ) w ( r ,6 3 ) , 其中共粘了( n 3 一1 ) 2 条n 由引理2 1 2 5 及事实2 1 、2 2 知,存在g l 的一组整和标号妒l ,对任 意z ( g i ) ,满足妒l ( z ) 一妒l ( r ) ,2 妒l ( r ) ,且妒i o 由引理2 6 ,依次粘合其于长不小于4 的路于n 可得图g ,且知g 是整 和图 圈a 。是具有顶点集y = h 口2 f 8 。) 和边集昱= f 8 1 n 2 ,8 。一l n l 的图 推论2 1 圈g m 5 ) 与广义星的中心或悬挂点粘合所得的图是整和 图特别地,矗与星粘合的图是整和图 证明据【1 7 】,如= g + ( 1 ,2 ,一1 3 一2 ) ) 岛= g + ( t 1 ,4 ,一3 一l ,5 ,一4 ) ) , o ;g + ( 1 ,2 ,一5 7 ,一3 4 ,3 ) ) e 8 = g + ( l ,5 ,2 7 一2 9 ,一8 ,6 ”, i 为一g + ( 3 ,4 ,一1 5 ,一1 2 ,1 7 。一7 1 0 ,7 ) , 山东师范大学硬士学位论文 g 盅g + ( d i ,衄,8 。- 4 ,一_ 5 ,墙幻一- 3 t8 t l 一3 一n l ) 如1 0 ,其中口l = l ,n 2 = 2 ,哪= 啦一】+ 哪一2 ( 3 s t n ) , 因此如5 ) 是星和图且任意点可作为z 若z 与广义星的中心粘 合,则由定理2 ,2 知所得图为整和图;若z 与广义星( g ,r ) 的某个悬挂 点6 粘合,设( g ,r ) 中6 ,r 间的路为p ( 6 t r ) ,删去p 限r ) 后的广义星为 ( ,r ) ,则由引理2 1 ,( ,z ) w ( p ( 6 ,r ) ,6 ) ;( ,r ) 是关于r 的星和图,再由定 理2 2 ,( ,r ) w ( ,r ) 是整和图,从而推论得证 定理2 3 圈伤不是星和图,但仍与星局,。的中心的粘合图为整和 图 证明因为仍含有饱和点,所以对它的任一组整和标号s 有o s 所 以凸不是星和图 给出一组标号: s = n l = o ,0 2 = 一1 ,口3 = 1 ,= 2 i + 1 ( 1 i 曼n ) 可证得s 是伤与星的中心的粘合图的一组整和标号 定理2 ,4 圈。不是整和图,但圈a 与星蜀,。b 2 ) 的中心的粘合 图是整和图 证明由1 3 】知( ( a ) = 3 ,所以圈q 不是整和图 给出下面一组标号: 令s = 如l = 一2 ,n 2 = 2 n + 4 ,幻= 2 n ,b = 2 n + 2 ,氟= 2 行+ 4 + 2 i ( 1s i 器) 下证s 为( q ,n i ) ( 。,邱) ( n22 ) 的一组整和标号 ( 1 ) 因为n l 珊 口4 幻 司 功 z n ,所以幻+ q s n 4 + 4 f l + 8 2 n ,所以0 4 + s 当ls i z 。,所以啦+ q 聋s 综上可知,( c 4 ,n - ) w ( 甄。,z o ) ( n 2 ) 是整和图 命题2 3 p 1 j 若s 为g 的一组整和标号,则m s 也是g 的整和标号,其 中m 为非零的整数 命题2 ,1 圈a 与星n ,的中心的粘合图不是整和图 证明假设( 瓴,n i ) m ( 趣,l ,却j 是整和图设s 是( q j 。1 j w ( 硒。l ,z o j 的 一组整和标号 由对称性,不妨设n : 且s 中绝对值最大的点标号为正数,否则 由事实2 3 知一s 为满足条件的一组整和标号 分下面四种情形讨论: ( i ) 若胡为s 中的最大标号点时,则n l o 若印 o ,贝口l + 4 o 且口l + 口4 d 3 口2 口4 o 由( a ,d i ) ( 1 1 知) 是整和图,则n 2 + 8 3 = 口3 + 。4 = “矛盾 山东师范大学硕士学位论文

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论