图中具有特定条件的点不交的圈

发布时间：2017-08-23 12:11

  本文关键词：图中具有特定条件的点不交的圈

  更多相关文章： 图 圈 点不交 二分图

【摘要】：本文主要介绍图中具有特定条件的点不交的圈。图G中含有k个顶点的路或圈分别记为k-路或k-圈。若一条路(或一个圈)包含图G的全部顶点,则称这条路(或这个圈)为G的Hamilton(哈密尔顿)路(或Hamilton圈)。图中点不交的圈的问题是著名的Hamilton圈理论的一个推广。Catlin (Ph. D.Dissertation.Ohio State University,1976),Aiger,Brandt(J.London Math.Soc,1993,48(2):39-51)和Alon(Discrete Math.,1996,152(1):13-23)分别给出了图中含点不交的圈的度条件。1984年,El-Zahar给出了下列猜想：设G是一个含有n=n1+n2+…+nk(ni≥3,1≤i≤k)个顶点的简单图,若则G包含κ个点不交的圈C1,C2,…,Ck,其长度分别为n1,n2,…,nk.此猜想至今未得到解决。但是El-Zahar在同一篇论文中证明了k=2时的情况：设G是一个含有n=n1+n2个顶点的简单图,若则G包含两个点不交的圈C1,C2,其长度分别为n1,n2。2009年,Gao,Yan和Li(J.Appl.Math.Comput.2009,31:203-215)给出了二分图中包含特定点的点不交的圈问题的度条件。本文中证明了如下结果：结果1：设G是一个含有n个顶点的简单图,若对G中任意两个不相邻的点x,y,有d(x)+d(y)≥n+4,则对任意的(n1,n2),ni≥2,n=n1+n2,G包含两个点不交的圈C1,C2,其长度分别为n1,n2。结果2：设k是一个正整数,G是一个含有n≥4k个顶点的简单图。若对于G中任意一对不相邻的点x,y有max{d(x),d(y)}≥2k,则G包含κ点不交的圈。结果3：令G=(V1,V2,E)是一个二分图,|V1|=|V2|=n≥2k+1,其中k≥1是一个整数。若对G中任意两个不相邻的点x∈V1,y∈V2,有d(x)+d(y)≥n+k,则对G中的任意k个不同的点v1,v2,…,vk,G都包含k-1个点不交的4-圈C1,C2,…,Ck-1和一条含有2t个顶点的路Pk,其中t=n-2(k-1),使得每个圈和路Pk中都包含一个特定的点。结果4：令G=(V1,V2,E)是一个二分图,|V1|=|V2|=n≥2k+1,其中k≥1是一个整数。若对G中任意两个不相邻的点x∈V1,y∈V2,有d(x)+d(y)≥n+k,则对G中的任意k个不同的点v1,v2,…,vk,G都包含k个点不交的圈C1,C2,…,Ck,使得每个圈中都包含一个特定的点,并且这k个圈中有k-1个是4-圈。
【关键词】：图 圈 点不交 二分图
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 中文摘要6-8
• 英文摘要8-10
• 符号说明10-11
• 第一章 前言11-21
• §1.1 基本概念11-13
• §1.2 图中的圈理论的发展13-21
• 第二章 图中的2-因子21-29
• §2.1 主要结果21-22
• §2.2 相关引理22-26
• §2.3 定理2.1.1的证明26-29
• 第三章 图中点不交的圈29-38
• §3.1 预备知识及定理29-30
• §3.2 相关引理30-33
• §3.3 定理3.1.1的证明33-38
• 第四章 二分图中点不交的圈38-50
• §4.1 预备知识及定理38-40
• §4.2 相关引理40-43
• §4.3 定理的证明43-50
• 参考文献50-54
• 致谢54-55
• 已完成和发表的论文55-56
• 学位论文评阅及答辩情况表56

【相似文献】

中国期刊全文数据库 前10条

1 杨宏晨;关于k-消去二分图的一些结果[J];数学的实践与认识;2003年11期

2 杨宏晨,薛秀谦;二分图为k-消去图的 2个条件(英文)[J];Journal of Southeast University(English Edition);2003年02期

3 李峰;耿建艳;李硕;梁峰;;一种用4-圈和8-圈对二分图的划分[J];山东大学学报(理学版);2008年06期

4 王宏祥,苏磊,车文刚;二分图的无关分解[J];云南工业大学学报;1998年01期

5 车军领;关于二分图的2-因子[J];山东师大学报(自然科学版);2000年03期

6 钱建波;二分图中k-因子存在的两个充分条件[J];山东大学学报(自然科学版);2001年04期

7 颜谨;二分图中相互独立的圈[J];山东大学学报(理学版);2002年05期

8 石建军;何大韧;;二分图的投影、边权及点强度[J];商丘师范学院学报;2009年09期

9 汪小玲;;满足某些不等式条件的置换与二分图[J];西南师范大学学报(自然科学版);2010年03期

10 周磊;支蓉;冯爱霞;龚志强;;基于二分图的温度网络拓扑性质研究[J];物理学报;2010年09期

中国重要会议论文全文数据库 前2条

1 杨楠;丁晖;刘悦;;Web社区紧密核的抽取方法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

2 付春花;刘爱芬;陈卓辉;何大韧;;合作-竞争网络的二分图描述建议[A];中国数学力学物理学高新技术交叉研究学会第十二届学术年会论文集[C];2008年

中国博士学位论文全文数据库 前1条

1 高云澍;图中存在独立圈及指定条件因子的度条件[D];山东大学;2009年

中国硕士学位论文全文数据库 前10条

1 朱文;基于时序二分图的优化派工方法研究及Web实现[D];南京理工大学;2015年

2 张绍华;图中具有特定条件的点不交的圈[D];山东大学;2016年

3 鲁富荣;二分图的因子[D];山西大学;2007年

4 刘琼;包含大圈的2-因子在二分图中的存在性[D];江西师范大学;2007年

5 朱琅;基于二分图的查询推荐算法[D];安徽大学;2014年

6 郑思远;基于二分图的混合推荐系统的研究与实现[D];北京邮电大学;2015年

7 李改枝;基本极大（m+1）K_2-free二分图[D];河南大学;2009年

8 蔡莹莹;基于二分图的应急预案体系有效性研究[D];大连理工大学;2012年

9 李金娜;关于图的[k，，k+1]-因子的若干结果[D];东北大学;2006年

10 李峰;图的独立圈和2-因子理论的几个最新结果[D];山东大学;2009年

本文编号：724964