足球比分直播

图上点不交子图的参数条件.pdf

返回
图上点不交子图的参数条件.pdf_第1页
第1页 / 共36页
图上点不交子图的参数条件.pdf_第2页
第2页 / 共36页
图上点不交子图的参数条件.pdf_第3页
第3页 / 共36页
图上点不交子图的参数条件.pdf_第4页
第4页 / 共36页
图上点不交子图的参数条件.pdf_第5页
第5页 / 共36页
点击查看更多>>
资源描述:
宁夏大学硕士学位论文 英文摘要ABSTRACTThe history of graph theory research has already been two hundred years.Since thefifties and sixties of the twentieth century,graph theory has developed very fast and numerousin scientific field.Moreover,as a important subfield in discrete mathematics,graph theoryis not only used in mathematics and computer science,but also widely applied in chemistry,traffic management,communication engineering and other disciplines.Now it has attractedmore and more attention from all perspectives.All graphs in this paper are considered only finite,simple,undirected graphs with noloops and no multiple edges.Let G be a graph,a hamiltonian cycle is a cycle which containsevery vertex of G.Given a cycle G of G,if GECjoins two vertices of C,then itis called a chorded cycle.A theta graph is the union of three internally disjoint paths thathave the same two distinct end vertices.The Hamiltonian problem is one of the most famousproblems in graph theory,it has got a lot of results SO far.In this paper,we mainly concernabout the following problemsthe graphs containing independent cycles which have specified lengths,bipartite graphs containing independent cycles with specified lengths and theexistence conditions for 0-graphs.This paper is divided into four chapters.In chapter l,we introduce some basic notations,the history and the progress of the cycle theory,and the primary results about the paper.In chapter 2,we consider bipartite graphs containing independent cycles with specifiedlengths.In chapter 3,we proof the theoremsuppose Gv1,%;Ebe a bipartite graph withlⅥIIKI3k.If 6G≥2k,then G contains七一1 disjoint 6-cycles and a path of order6 such that all of them are disjoint.Similarly,we have another resultif 6G≥2k,thenG contains七diSjoint 6-cycles or七一1 disjoint 6-cycles and a quadrilateral such that all ofthem are diSjoint.In chapter 4,we investigate the existence of three O-graphs,it is the innovation point ofthis paper.The main result is as followingevery graph of order几≥12 and size at least【旦铲J contains three disjoint theta graphs.Moreover,we obtain a corollaryevery graphof order礼≥12 and size at least l半产J contains three disjoint cycles of even length.Furthermore,in the end of every chapters,we list some problems for future research anddiscussions.Key Words Independent cycles;Bipartite graph;O-graphs;Vertex disjoint一Ⅱ一宁夏大学硕士学位论文 目 录目 录摘要IABSTRACT英文摘要.Ⅱ主要符号对照表..Ⅳ第一章引言..11.1基本概念11.2问题产生的背景及进展...21.3已有结论及本文结果6第二章图中包含指定长度独立圈的度条件....82.1引言及引理82.2定理2.1.2的证明.92.3可进一步讨论的问题12第三章二部图中包含指定长度独立圈的度条件..143.1引言及预备知识.143.2相关引理163-3主要定理的证明.173.4小结.20第四章图中包含指定个数臼图的参数条件..214.1引言及预备知识.214.2主要定理的证明.234.3可进一步讨论的问题......31参考文献...33致谢.....36研究生期间的研究成果一..37一Ⅲ一宁夏大学硕士学位论文 主要符号对照表GK EEGYa6GAG仃2Gdv,HNv,HEG1,G2GVK。tClPM【XJ主要符号对照表一Ⅳ一顶点集为y边集为E的图G图G的边集图G的顶点集图G的最小度图G的最大度图G中不相邻顶点的最小度和点V在子图日中的度点V在子图H中的邻域连接G。中点和G中点的边集图G的由G一{u}导出的子图阶数为孔的完全图圈C的长度路P的长度不小于z的最小整数不大于X的最大整数宁夏大学硕士学位论文 第一章引言1.1基本概念第一章 引言图中点不交子图的存在性研究是图论中的一个重要领域.路和圈作为图中的基本子图,利用度条件作为限制条件来研究图中点不交子图的存在性问题,人们已经得到了许多非常有意义的结果,可参考综述文献【1].本章共有三节,第一节介绍了一些在本文中用到的图论定义及术语,未说明的图论术语在其他章节中必要时再给予阐述.第二节主要介绍圈理论的历史背景和进展状况.第三节简单介绍一些已有的相关结论以及本文的主要结果.我们首先介绍一些图论的基本术语,其它未说明的定义和术语参考文献f2].我们通常称二元集合GGyG,EG为一个图,其中yG称为顶点集,Va中的元素称为图G的顶点,EG为边集,EG中的元素称为图G的边.IyGI1且IEGlo的图我们称为平凡图,其它图称为非平凡图.图G的阶是指VG的顶点个数IVGI,而lEGi称为图G的边数.对于图G的两个顶点乱和u,如果eUV∈EG,则称U和“相邻,乱,V互为邻点,且称札和V是边e的端点,u和V分别与边e相关联.若图G的边e。和e。有一个公共端点,则称边e1和e2相邻.对于一个图,如果没有环也没有重边,则称该图为简单图.若无特殊声明,本文所涉及的图均为简单无向有限图.对于图G,我们用dG钉或d㈦G表示顶点V在G中的度数.△G和6G分别表示G的最大度和最小度。在不引起混淆的情况下可简记为△和6.我们称日为G的子图,如果VH∈yG,EH∈EG.设H为G的子图,如果VHyG,则称日为G的支撑子图.对于图G的子图H,用G[y日]或G【日]表示日在G中的点导出子图.如果日是G的一个子图,那么对于任意z∈vc一y日,有%zⅣGzn y日.设口和日分别是G中的一个顶点和G的一个子图,用Nv,日代表日中和V相邻的点的集合,令d创,HINv,HI,用G一日表示G[VG一y日].对于非完全图G,定义a2amin{dzduxy隹EG;如果G是完全图,则令盯2G00.点集X。,z,,zk称为图G的一个独立集,如果它们中的任意两点之间没有边,图G的最大独立集所包含的顶点数,称为图G的独立数,记为aG.我们称图G的子图集合是相互独立的或者点不交的,当且仅当其中的任意两个子图在G中没有公共的交点.对于图G的两个点不交子图G。和G2,EGl,G2表示图G中连接Gl中的点和G2中的点的边集合,令eG1,G2IEG1,G2I.图G中一个点边交替出现的序列如刨v%e{,vi,eteE。vi。称为途径.边不重的途径称为迹.顶点不重复的迹则为路.起点和终点相同的路即为圈.图中路和圈的长度指的是它们边的条数.哈密顿圈是指图G中包含G的所有顶点的圈.在一个圈中,如果圈上不相邻的两点之间有边,则称这个圈为弦圈.设v1,u。,,‰是G中k个一1一宁夏大学硕士学位论文 第一章引言不同的顶点,G,岛,,G为G中k个相互独立的圈,使得q,Q,,q在G中分别包含“1,创2,,仇,则称G关于{u1,V2,,Vk包含七个相互独立的圈G,Q,,G.如果存在yG的两个点不交子集Ⅵ,K,使得ycvi u K,且G的所有边均有一个端点在Ⅵ内,另一个端点在%内,那么称G为二部图,也称为二分图,记作GⅥ,v2;EG,简记为GⅥ,K.如果IⅥl1%J,则称G为均衡二部图.对于二部图,我们给出两种度和条件,定义如下巧1,1Gmin{dexdgy]x∈M,Y∈%盯1,1Gmin{dGzdGylz∈Ⅵ,Y∈K,xy譬EG对于yG的一个子集u,如果U中任意两点均有边连接,则称G[卅是完全图.如果G是一个完全二部图,则盯1.1GOO.完全二部图‰,。是指剖分集阶数分别为m和佗的二分图,并且不同剖分之间的任意两个顶点之间均有边,即l‰。。lmn.同构于K,,3的图我们称之为爪,不包含爪的图称为无爪图.G的两个顶点¨和V称为连通的,如果G中存在u,勘路.显然,连通是yG上的一个等价关系.根据每一个等价类,可确定图G的一个点导出子图,我们称之为G的分支.若G只有一个分支,则称G是连通的;否则,称G为非连通的.G的连通分支个数记为尼G.除了上述基本定义和术语,在每章必要时会给出一些特殊定义和术语.为了方便阐述,有时可能会重复某些定义.1.2问题产生的背景及进展图的哈密顿圈问题是图论研究中著名的问题之一,哈密顿圈是只有一个分支的2一因子,它是图的独立圈领域的一个基本问题.关于哈密顿圈度条件的结果已经有很多.首先,给出两个最经典的结论定理1.2.1[3]设G是一个顶点数为扎的图,其中佗≥3.如果最小度占G≥号,则G是哈密顿图.定理1.2.2【4】设G是一个顶点数为礼的图,其中礼≥3.如果最小度和盯2G≥n,则G是哈密顿图.上面的两个定理,我们通常称为Dirac条件和ore条件.之后,范更华在[5]中证明了设G是一个顶点数为礼的2.连通图,其中礼≥3,如果对于任意两个距离为2的点札,u,maX{du,d口≥42,则G包含了一个长度至少为min{n,c】-的圈.不难看出,一2一一二一宁夏大学硕士学位论文 第一章引言当c咒时,G包含哈密顿圈.1963年,Moon和Monser在[6]中,得到了两个二部图中包含哈密顿圈的结果定理1.2.3【6]设G是一个顶点数为2礼的平衡二部图,如果最小度JG≥下nl,则G是哈密顿图.定理1.2.4【6]设G是一个顶点数为2n的平衡二部图,如果盯1,la≥n1,则G是哈密顿图.除了上述定理外,还有许多关于哈密顿圈的结果,可参考文献[7】.作为哈密顿图的推广,人们很自然地考虑图的独立圈和2一因子问题,主要集中在以下几个方面图中包含指定个数的独立圈和2一因子;图中包含指定长度的独立圈和2一因子图中具有指定性质的独立圈和2.因子等.Corrddi和Hajnal在[8]中探索了图中包含独立圈的最大个数,并给出了最小度条件定理1.2.5[8]设G是一个顶点数为礼的图,如果n≥3k并且6G≥2k,那么G包含k个独立圈.由以上结果我们可以看出,G的阶数等于3七时包含了后个相互独立的三角形.Justesen在[9]qb将此条件进行了推广定理1.2.6【9]设G是一个顶点数为礼的图,如果礼≥3k并且盯2G≥4k,那么G包含七个独立圈.J.Verstrae在【14],Y.Egawa在[15]中证明了k≥2时存在正整数礼k,使得阶数至少为礼k并且最小度至少为2七的图包含k个相互独立的圈,并且这k个圈的长度相等.之后,Erd6s和Faudree在[16】中提出了一个猜想如果图G的阶数佗4k且6G≥2k,则G包含了七个相互独立的四边形.Wang在[17,18]中,解决了此猜想.另外,Enomoto在[10】,Wang在[11】中,分别将定理1.2.6中的条件盯2G≥4k改进为0“2G≥4k一1.Brandt等人在『121中证明了定理1.2.7[12】BG是--个顶点数为礼的图,如果n≥4k且a2G≥ /2,则G有一个2-因子恰好包含七个独立圈.之后,Fujita,Tsugaki和№lashita在【13】中将上述结果推广到了盯3G一3一宁夏大学硕士学位论文 第一章引言定理1.2.8【13]设G是一个顶点数为n≥3k2的图,其中后≥2是一个正整数.如果盯3G≥6k一2,则G包含尼个独立圈.关于二部图中指定个数独立圈问题的研究,1996年waJlg在[19]中考虑了二部图中包含k个独立圈的条件定理1.2.9[19]设GⅥ,%;E是--个二部图,后是正整数,IⅥII%In≥2k1如果占G≥七l,则G包含尼个相互独立的圈.1999年,Wang在[20]中又将上述条件改进,得到了一个包含k个独立圈的2.因子定理1.2.i0[20]设GⅥ,K;E是一个二部图,满2lVll1%In2k,其中后是一个正整数.如果图G的最小度至少为『鸶]1,则G包含一个2一因子,且此2一因子恰好包含k个分支.2009年,颜谨和高云澍在【21]中将定理1.2.9的结果进行推广,证明了定理1.2.1】[21】设GⅥ,%;E是一个二部图,lⅥ|礼1,I%In2,满足n1≥2尼1,n2 2 2kl,其中七,nl,71,2是三个正整数.如果盯1,1G≥2k2且l扎1一n2I≤1,则G包含了k个相互独立的圈.图中的弦圈是指至少包含一条弦的圈.P6sa在[22]中最先考虑了关于弦圈的问题并且证明了,最小度至少为3的图包含弦圈.2008年,Finkel在[231考虑了图中包含七个独立弦圈的条件,得到了如下结果定理1.2.12[23]NG;黾--个图,满足IyGI≥4k,如果最小度至少为3尼,则G包含七个独立的弦圈.Bialostocki等人在[24】中基于以上结果,将圈及弦圈相结合,提出了以下猜想猜想1.2.13[24]设r,s是两个非负整数,G是一个图,满足IyG『≥3r4s.如果最小度6G≥2r3s,则G包含r个圈和s个弦圈,且它Yf]Ni相独立.关于此猜想,Bialostocki等人在【24]中解决了7 0,s2以及s1的情况.对于更一般的情况,Chiba等人在[25】中证明了一个比此猜想更强的结果对于一个顶点数至一4一宁夏大学硕士学位论文 第一章引言少为37’4s的图G,如果盯2G≥4r6s一1,则G包含了rs个独立圈,其中s个是弦圈.还有更多关于弦圈的结果,可参考文献[261.下面,我们简单介绍一些图中包含指定长度独立圈问题的研究背景.1984年,EIzallar在[27]中证明了下面的结果定理1.2.14[27】设G是一个图,㈣kIVGIn1竹2,其中孔1≥3,n2≥3为两个整数,如果6G≥『警]『等],则G包含了两个独立圈c,和G,其长度分别为n·和扎.同时,EIZahar在[27]中提出了一个著名的猜想猜想1.2.15[2 7]设G是一个图,其顶点数为礼n1n2nkhi≥3,如果占G≥『等1『警1『等],那么G有七个独立圈q,岛,,瓯,其长分别为n-,722,,nk.w抽g在[28]中证明nt3i1,2,,七时上述猜想成立.Enomoto在【29]中用盯代替6得到了定理1.2.16[29】设G是阶数为n的图,满足n≥3k3,并且盯2G≥几十尼,则图G有一个2一因子,包含了尼1个独立圈G,岛,,Gl,使得对所有g]1≤i≤七,有IG『3.当几ln2他%4时,猜想1.2.15变为Erd6s和Faud眦在[30,31】中的猜想,此猜想被Wang在[32]中证明定理1.2.17[32】设G是一个图,顶点数为礼4k,其中后是一个正整数.如果6G≥2k,则G包含了后个独立的4.圈.关于此猜想,人们已经得到了很多相关结果.如JohaIlsson在【33]中就证明以下定理定理1.2.18[33】设G为一个图,顶点数为礼4k,其中七是一个正整数.如果巧G≥2k,则G包含了七一1个独立的4一圈和一条4长路,且这些圈和路都是相互独立的.为便于研究问题,人们试着将其最小度条件降低,也得到了许多相关结论.如2005年,Zhang和Wang在[34】中给出了以下结果定理1.2.19[34]图G的顶点数n4k,其中七是一个正整数.9a果5G≥2k一1,则G包一5一宁夏大学硕士学位论文 第一章引言含k一1个独立4.圈.1997年,Brandt等人在[351将3-N4-圈放在一起研究,得到了以下结果定理1.2.20[35]设G是一个顶点数为nN图,满足n≥3s4ks并且s≤k.如果口2G≥ns,则G包含k个独立圈c1,G,,G,满足l≤i≤sN,laI3;so并且扎3s4t,G是一个顶点数为礼的图.如果占G≥下ns,则G包含st个独立圈,其中s个是3一圈,£个是4一圈.上述结果也表明,对所有3≤他≤41≤i≤七,EI-Zahar在【2 7】中的猜想是成立的1.3已有结论及本文结果第二章,主要研究图中包含指定长度独立圈的问题.关于图G的三圈覆盖问题,Li在[371已经得到了以下结论定理1.3.1【37]设k,扎是两个正整数,G是一个顶点数为佗≥3k的图,x是G中七个不同点的集合.如果6G≥警,则G包含了尼个独立的三圈使得每个圈包含且只包含x中的一个点.Gao等在[42]中证明了定理1.3.2[42】设克,扎是两个正整数,G是一个顶点数为扎≥3k1的图,x是G中七个不同点的集合.如果对于G中任意两个不相邻的点z,Y,都有盯2G≥n2k一2,则G包含了尼个相互独立的圈c1.,G,使得每个G1≤i≤七包含且只包含x中的一个点,其中1≤i≤七时,IGl3,或1≤i七时lG『3,Ic,I4.第三章,主要讨论二部图中包含指定长度独立圈问题.关于二部图中包含独立6一圈的结论有定N1.3_3【38]GⅥ,K;E是二部图,IⅥII%l3k,尼是一个正整数,如果盯1,lG≥4kl,那么G包含k一16一圈和一条6一长路,并且它们均互相独立.一6一宁夏大学硕士学位论文 第一章引言定理1.3.4[39】GⅥ,K;E是二部图,lⅥII%I3k,七是一个正整数,如果aa≥2七一1,那么G包含七一1个独立的6.圈.我们在此基础上进一步推广,证明了以下结论定理1.3.5 Gv1,%;E是二部图,lⅥl1%I3k,尼是一个正整数,如果占G≥2k,那么G包含七一1个6一圈和一条6一长路,并且它们互相独立.类似地,我们还得到了另一个结果定理1.3.6 GⅥ,%;E是二部图,IⅥlIⅥI3k,七是一个正整数,如果占G≥2k,那么G包含了七个独立的6一圈或者七一1个6一圈和一个4.圈,且它们互相独立.第四章,主要考虑图中包含指定个数独立臼一图问题.Gao和Ji在[40]中考虑了图中包含最大个数独立p一图的条件,提出了相关猜想,并证明了七2的情况定理1.3.7[40]每个阶数n≥8且边数为,咒的图包含两个点不交的口一图,其中跏-f 23 舻8、7 【【7n一13/2jn≥9我们在此基础上,进一步讨论图中包含三个独立口一图的条件,证明了以下结果定理1.3.8任意阶数礼≥12且边数至少为【坐产J的图包含三个相互独立的口-图.作为推论,我们还得到了另一个结果推论1.3.9任意阶数n≥12且边数至少为l掣J的图包含三个相互独立的偶圈.一7一
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播