图二部平衡划分中的极小反例问题

发布时间：2017-10-23 23:13

  本文关键词：图二部平衡划分中的极小反例问题

  更多相关文章： 图 k-部划分 k-部平衡划分 二部平衡划分

【摘要】：设图G为简单图,k为正整数.若将图G的顶点集V(G)划分成k个互不相交的顶点集V1,V2….,Vk,称为简单图G的一个k-部划分.若图G的某个k-部划分,满足条件-1≤|Vi|-|Vj|≤1,(i,j∈{1,2,,…,k}),则称V1,V2….,Vk,是图G的一个k-部平衡划分,其中|Vi|(i∈k)表示某个划分的大小即所含顶点个数.本篇学位论文主要讨论k-部划分中比较特殊的平衡二部划分问题,即此时k=2.在文献中,Bollobas和Scott有一个著名的关于平衡二部划分的猜想：对于有m条边和n个顶点的简单图G,若每个顶点的度至少为2,则图G存在一个平衡二部划分[V1,V2],使得max{e(V1),e(V2)}≤m/3.Xu,Yan和Yu在文献中初步证明了当时,图G的最大平衡二部划分满足]max{e(V1),e(V2)}≤e(G)/3.之后,Xu和Yu进一步证明猜想的正确性,并指出三角形K3是唯一极图.Lee,Loh和Sudakov证明了对任意正整数k≥1,每个有m条边的图G,若最小度为2k或2k+1,则图G有平衡二部划分[V1,V2]满足(?)并且他们猜想无穷小的尾数项可以去掉.本篇学位论文延用Xu和Yu在文献中的方法,主要证明了如下结论：设图G是一个最小度不小于4且含m条边和几个项点的简单图.若图G没有二部平衡划分[S,S],使得(?)但任一最小度不小于4且阶数小于n图H都有二部平衡划分[T,T]使得(?) u1,u2,u3,u4为四个4一度点且G[{u1,u2,u3,u4}]=K4,则有(?)除非其结构为图1和图2
【关键词】：图 k-部划分 k-部平衡划分 二部平衡划分
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要5-7
• Abstract7-9
• 第1章 绪论9-18
• 1.1 相关定义和概念9-11
• 1.2 图划分的历史进展和现有结论11-16
• 1.3 本文所用相关结论16-18
• 第2章 定理及证明18-37
• 第3章 总结与展望37-38
• 参考文献38-41
• 致谢41

【相似文献】

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

1 苏本堂,扈文峰;最小度和f-因子[J];山东大学学报(自然科学版);1997年02期

2 刘红霞;k-对等图的邻集和最小度[J];烟台大学学报(自然科学与工程版);2002年02期

3 陈纲;;蕴含扇图的可图序列的最小度和[J];西北师范大学学报(自然科学版);2006年04期

4 张勇飞;柳明珠;;关于包含2个圈的2-因子的最小度条件的注记[J];科教文汇(下旬刊);2008年11期

5 滕岩;王江鲁;;图的最小度与路可扩性[J];科学技术与工程;2010年11期

6 蔡小涛;关于S-闭迹的最小度的充分条件[J];数学年刊A辑(中文版);1989年03期

7 李明楚,李忠祥;无爪图中的最长圈[J];数学研究与评论;1993年01期

8 滕聪;k-消去图的邻集和最小度[J];临沂师专学报;1993年Z1期

9 任世军,罗声政;邻域并与最小度给出的哈米顿图的充分条件(英文)[J];哈尔滨工业大学学报;1993年01期

10 苏本堂,何乐亮,程述汉;独立数和最小度与f-因子[J];山东师大学报(自然科学版);1997年01期

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

1 何蓓;吴敏;三间均;周意诚;;基于最小度排序的One to One营销优化算法[A];第二十三届中国控制会议论文集（上册）[C];2004年

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

1 刘建熙;关于Randic指标三个问题的解决[D];南开大学;2010年

2 邹青松;图包含指定长度的圈和泛弧问题的研究[D];山东大学;2011年

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

1 肖然;图二部平衡划分中的极小反例问题[D];南京师范大学;2016年

2 刘建熙;[D];华南师范大学;2007年

3 滕岩;图的度与路可扩性[D];山东师范大学;2010年

，

本文编号：1085853