论文摘要
对超图给定一定的限制条件去研究超图的某些参数的界是图论中一个经久不衰的问题.在本文中,在前人的基础上,我们研究了几个具体的极值类问题.本文的内容主要包括以下几个方面:在绪论中,我们先给出了图论的一些基本概念和初等结果,接着我们阐明了研究的背景知识.第二章我们具体讨论一个Turán类问题.对于给定了最大度和匹配数的图,Chvatal和Hanson给出了它们边数的紧上界.Khare研究了线性3-图在给定匹配数和最大度的条件下边数的上界.在本文中,在限制匹配数和最大余度的条件下,我们给出了一般3-图边数的上界,且给出的极图说明了我们得到的上界是紧的.第三章考虑的是一个镶嵌问题.给定整数k和一个k-图F,令tk-1（n,F）表示满足以下条件的最小整数t:对于每个n点k-图H,如果它的余度不小于t,那么它包含一个F-因子.对于整数k≥ 3,0 ≤l≤k-1,令yk-1表示由正好相交l个点的两条边形成的k-图.Han和Zhao提出下面的问题:对于所有的k≥3,0≤l≤k-1和充分大的n,n要求能被2k-l整除,tk-1(n,yk-1)的确切值是多少?在本文中,我们给出了当k≥3且1≤l≤k-2时,tk-1(n,yk,l)的确切值.这个结果与之前Rodl,Rucinski和Szemeredi以及Gao,Han和Zhao的结果结合起来,就能给出Han和Zhao的问题的完整解答.第四章中我们构造了两个覆盖问题的极图.给定两个3-图F和H,H的一个F-覆盖是指H的一族F使得H的每个点都被包含在这些F中的至少一个中.令c2（n,F）表示满足以下条件的最大整数t:每个最小余度大于t的3-图都有一个F-覆盖.在本文中,我们将确定c2(n,K43-)和c2(n,K53-)的确切值,这里Kt3-是t个点上的完全3-图删除一条边所得到的图.由这些结果可知,一个由Falgas-Ravry和Zhao提出来的问题被完全解决了.一个悬而未决的猜想指出每个没有孤立点的n点图都包含一个顶点数至少为cn的诱导子图,使得这个子图的每个点度都是奇数,这里的c>0是某一个常数.Scott证明了每个图G都有一个顶点数至少为|V（G）|/（2/（G））的诱导子图,它的所有点度都为奇数,这里的x（G）是图G的染色数,这意味着上述猜想对于染色数有界的图是成立的.但有结果表明n前面的因子1/（2x（G））并不是最好的,Radcliffe和Scott证明了对于树,c=2/3,Berman,Wang和Wargo证明了对于最大度为3的图,c=2/5.所以对一些特殊类型的图,c值的确定会是一件很有意义的事.在第五章中,我们将证明对于树宽不超过2的图,c=2/5,而且这个界是紧的.
论文目录
文章来源
类型: 博士论文
作者: 余磊
导师: 马杰,侯新民
关键词: 极值类问题,镶嵌,覆盖,上下界,诱导子图
来源: 中国科学技术大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 中国科学技术大学
分类号: O157.5
DOI: 10.27517/d.cnki.gzkju.2019.000144
总页数: 82
文件大小: 3519K
下载量: 17
相关论文文献
- [1].关于诱导子树与图的色数的一个注记[J]. 中国科学:数学 2017(05)
- [2].p~2阶非正规Cayley图的核[J]. 数学进展 2018(05)
- [3].基于consR的并行图匹配方法[J]. 计算机技术与发展 2015(07)