论文摘要
设G是简单图,若我们将G的顶点集划分成两个互不相交的顶点集S,S,则称（S,S）为G的一个二部划分。设（S,S）为G的一个二部划分,若|| S |-| S ||≤1,则称（S,S）为G的二部平衡划分。本篇学位论文主要讨论带有边数条件限制的平衡二部划分问题。给定顶点子集S,我们用e（S）表示S导出子图的边数。在文献[4]中,Bollobas和Scott提出猜想:如果简单图G有m条边且最小度大于等于2,则图G存在平衡划分[S,S],使得max{e（S）,e（S）}≤m/3.之后,Xu和Yu在文献[19]中证实了Bollobas和Scott[4]的猜想,而且证明K3是唯一的极图。在文献[11]中,Lee,Loh和Sudakov证明了对于任意的正整数k≥1,如果图G有m条边且最小度为2k或2k+1,则G有平衡划分[S,S],使得max{e（S）,e（S）}≤（k+1/2（2k+1）+o（1））m,并且他们猜想无穷小的尾数项可以去掉。本篇学位论文是基于Lee,Loh和Sudakov[11]的结果,通过极小反例的方法,证明当k=4时,可以得到如下结论:定理:令X={F:δ（F）≥ 8,F的任意平衡划分[S,S]都有max{e（S）,e（S）}>5/18e（F）}.设G是X中点数最少的图,G中有8个8度点x1,x2,…,x8导出一个K8,e（G）三 r0（mod 18）,且设1)若|U1≤i≤8 N（xi）{x1,x2,…,x8} |=1,设x是x1,x2,…,x7及x8的唯一公共邻点,且d（x）=14时r0（?）{2,3,6,7,9,10,13,14,16,17},d（x）=15时r0（?）{3,7,10,14,17},2)若| U1≤i≤8 N（xi）{x1,x2,…,x8} |=2,设x与y是x1,x2,…,x7及x8在G-{x1,x2,…,x8}的邻点,xy（?）E（G）.且设|N（x）n{x1,x2,…,x8} |=a,|N（y）n{x1,x2,…,x8} |=b,并且设2.1)当a=7,b=1时,|（N（x）N（y））{x1,x2,…,x8} |≥1;2.2)当a=6,b=2时,|（N（x）N（y））{x1,x2,…,x8} |≥2;2.3)当a=5,b=3时,|（N（x）N（y））{x1,x2,…,x8} |≥3.则（?）.
论文目录
文章来源
类型: 硕士论文
作者: 王婉
导师: 许宝刚
关键词: 部划分,二部平衡划分,极小反例
来源: 南京师范大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 南京师范大学
分类号: O157.5
DOI: 10.27245/d.cnki.gnjsu.2019.002168
总页数: 43
文件大小: 1435K
下载量: 10
相关论文文献
- [1].政府间税收划分问题与改革对策[J]. 大众投资指南 2017(06)
- [2].限制的星划分问题[J]. 云南大学学报(自然科学版) 2008(02)
- [3].再论声乐教学中的声部划分问题[J]. 北方音乐 2015(20)
- [4].里海水域划分问题仍难以解决[J]. 中亚信息 2009(01)
- [5].加权复杂网络的社区划分问题研究[J]. 阴山学刊(自然科学) 2012(02)
- [6].若干图的r-色独立集划分问题[J]. 西北民族大学学报(自然科学版) 2011(02)
- [7].顶点赋权图中的连通子图划分问题[J]. 杭州电子科技大学学报(自然科学版) 2020(04)
- [8].乌克兰外交政策形成阶段的划分问题[J]. 乌克兰研究 2011(00)
- [9].论科学与非科学的划分问题及中医的科学性[J]. 艺术科技 2014(06)
- [10].矿区水文地质勘探中对灰岩含水层划分问题的思考[J]. 科技创业家 2013(14)
- [11].偶一致超图划分问题的若干结果[J]. 纯粹数学与应用数学 2014(01)
- [12].基于分豆策略的整数划分问题的设计与实现[J]. 福建电脑 2012(09)
- [13].日本关于俄日领土划分问题的研究[J]. 东北亚学刊 2017(06)
- [14].认知视角下英汉学习型词典中多义词义项划分问题初探[J]. 科技视界 2012(26)
- [15].有元素类型约束的k-划分问题研究[J]. 运筹学学报 2012(03)
- [16].限制性的带核元划分问题[J]. 云南大学学报(自然科学版) 2010(01)
- [17].我国地区间税权横向划分问题探究[J]. 税务研究 2009(06)
- [18].新时期北京党史阶段划分浅谈[J]. 北京党史 2015(01)
- [19].一种求解学区划分问题的混合启发式算法[J]. 测绘科学 2020(01)
- [20].论《史记·货殖列传》中经济都会的数目及等级划分问题[J]. 渭南师范学院学报 2012(03)
- [21].政府间养老保障责权划分问题研究[J]. 思想战线 2011(06)
- [22].书刊划分问题讨论综述[J]. 现代商贸工业 2010(22)
- [23].三划分问题可多项式归约为唯一可达向量Petri网可达性问题[J]. 微电子学与计算机 2008(10)
- [24].拉丁超立方体抽样遗传算法求解图的二划分问题[J]. 控制理论与应用 2009(08)
- [25].环上的最大最小路划分问题[J]. 甘肃联合大学学报(自然科学版) 2011(05)
- [26].谁在动创新者的奶酪?——“微”、“星”事件[J]. 中国科技财富 2009(05)
- [27].n元集合的无序k划分问题[J]. 中等数学 2015(07)
- [28].随机化均匀设计混合遗传算法求解图的二划分问题[J]. 智能系统学报 2009(01)
- [29].莫使哲学“空对月”——哲学怎样才是有用的?[J]. 现代国企研究 2011(04)
- [30].矩形的三角形划分问题研究[J]. 计算机工程与应用 2008(33)