论文摘要
极值图论主要研究在给定的图类中某些参数的最大值或最小值的问题,包括边数,最小度,直径,连通度等,并刻画取得最大值或最小值的极图.Turán型极值问题是极值图论中最典型的问题:求不包含给定的图H作为子图的图的最大边数和刻画对应的极图.谱极值图论主要研究与图相关联的各种矩阵,包括邻接矩阵,拉普拉斯矩阵,或无符号拉普拉斯矩阵等的谱性质,特别是不含有特殊子结构的图类中谱半径或者其他特征值和特征向量.本文重点讨论禁用线性森林的Erd?s-Gallai稳定性定理和禁用线性森林的邻接谱和无符号拉普拉斯谱极值结果.另外,还讨论禁用Ks,t子式的无符号拉普拉斯谱半径,并给出一个图是哈密顿连通的谱条件.·在第二章中,我们证明了关于最小度的Erd?s-Gallai定理的一个稳定性定理.令G是顶点数为n的连通图和F=（∪ii=1k1P2ai）∪（Ui=1lP2bi+1）是k+l条顶点数分别为2a1,...,2ak,2b1+1,...,2bz+1的点无交路,其中k>0,0≤1≤2,和k+l ≥2.如果最小度 δ（G）≥∑i=1kai+∑i=1l bi-1,那么对于充分大的n,除了一些特殊图类,必有F（?）G.这扩展和加强了 Ali和Staton对于偶路的结果,以及Yuan和Nikiforov对于奇路的结果.·在第三章中,我们确定了所有不含线性森林作为子图的图的最大谱半径和所有极图.另外,得到了二部图中所有不含kP3作为子图的图的最大边数和谱半径,并确定了所有极图.此外,还讨论了 Turán型极值问题与其谱对应问题之间的一些关系.·在第四章中,我们研究所有不含线性森林F作为子图且顶点数为n的图.我们先给出禁用kP3的稳定性定理,然后用这个稳定性定理确定了所有不含kP3作为子图的图的最大无符号拉普拉斯谱半径和所有极图.此外,我们也给出了所有不含线性森林F（F≠kP3且F至多含有两条奇路）作为子图的图的最大无符号拉普拉斯谱半径和所有极图.·在第五章中,我们证明了如果一个图G不含K2,t作为子式且顶点数为 n≥ t2+4t+1,其中 t ≥ 3,那么 q（G）≤1/2（n+2t-2+（?））,等号成立当且仅当n≡1（mod t）和G=F2,t（n）.特别地,如果t=3和n ≥22,那么F2,3（n）是唯一一个不含K2,3作为子式且顶点数为n的具有最大无符号拉普拉斯谱半径的图.此外,F,3（n）是唯一一个不含K3,3作为子式且顶点数为n≥1186的具有最大无符号拉普拉斯谱半径的图.·在第六章中,我们证明了如果顶点数为n充分大且最小度δ（G）≥k≥2的图的边数至少为1/2（n2-（2k-1）n+2k-2）,那么除了一些特殊图类,必有图G是哈密顿连通的.并且进一步用谱半径和无符号拉普拉斯谱半径给出了一个图是哈密顿连通的谱半径和无符号拉普拉斯谱半径条件,这拓展了 Zhou和Wang[96]的结果.
论文目录
文章来源
类型: 博士论文
作者: 陈明珠
导师: 张晓东
关键词: 定理,线性森林,最小度,谱半径,无符号拉普拉斯谱半径,二部图,子式,边数,哈密顿连通
来源: 上海交通大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 上海交通大学
分类号: O157.5
DOI: 10.27307/d.cnki.gsjtu.2019.000733
总页数: 125
文件大小: 4140K
下载量: 33
相关论文文献
- [1].“几何图形”检测题[J]. 中学生数理化(七年级数学)(配合人教社教材) 2016(12)
- [2].美丽的相遇[J]. 小学生导刊(高年级) 2017(05)
- [3].边数较少时度方和达到次大值的二部图[J]. 纺织高校基础科学学报 2013(02)
- [4].根图的稳定性及其优化[J]. 西南师范大学学报(自然科学版) 2017(04)
- [5].加强学习补差距[J]. 小学生学习指导 2018(26)
- [6].求受顶点数限制的所有最短路径的一个算法[J]. 广西教育学院学报 2012(03)
- [7].求图中受顶点数限制的所有最短路径的算法[J]. 计算机工程与设计 2008(07)
- [8].隐匿顶点数和边数的保密图形相似性判定[J]. 新疆大学学报(自然科学版) 2018(03)
- [9].欧拉公式的妙证[J]. 中学生数理化(八年级数学)(配合人教社教材) 2014(Z2)
- [10].正则c-部竞赛图中过指定顶点数目的路[J]. 太原师范学院学报(自然科学版) 2011(02)
- [11].基于OpenGL索引顶点数组的大尺度海面LOD算法[J]. 同济大学学报(自然科学版) 2009(03)
- [12].关于[4.8.8]铺砌中椭圆上D-点数的研究[J]. 河北科技大学学报 2017(02)
- [13].OpenGL ES在Android平台上3D绘图的两种方式分析与实现[J]. 硅谷 2013(12)
- [14].时间传播网络中受影响顶点的预测[J]. 计算机工程 2018(02)
- [15].几乎导出匹配可扩图的一些度条件[J]. 中国计量大学学报 2020(01)
- [16].偶图中相互独立的4-圈和6-圈[J]. 山西大同大学学报(自然科学版) 2015(04)
- [17].也谈该严谨时且严谨[J]. 中小学数学(初中版) 2014(Z2)
- [18].握手问题与几何体棱数、顶点数的求法[J]. 初中生世界 2014(45)
- [19].数学的简洁美[J]. 中学生数理化(高一版) 2008(09)
- [20].任意连通图与偏k-树乘积图的树宽[J]. 河南科技大学学报(自然科学版) 2008(01)
- [21].完全图的生成树中的完全m叉树[J]. 湖南文理学院学报(自然科学版) 2011(03)
- [22].利用顶点反馈集防御网络拆解攻击[J]. 科学技术创新 2018(14)
- [23].边数很少时二部图度方和的次大值[J]. 纺织高校基础科学学报 2010(01)
- [24].给定直径的树的和连通指数[J]. 三峡大学学报(自然科学版) 2010(05)
- [25].一种Douglas-Peucker加速算法[J]. 科技信息 2009(20)
- [26].d-退化图松弛均匀着色的一个注记(英文)[J]. 昆明学院学报 2011(06)
- [27].寻找图中两顶点间最长路径的算法设计[J]. 电脑编程技巧与维护 2018(07)
- [28].不含3,4-圈的平面图的均匀染色[J]. 科学技术与工程 2010(27)
- [29].OpenGL3.0新技术及其应用研究[J]. 计算机与网络 2009(16)
- [30].二部图匹配的一个判别条件[J]. 河南科技大学学报(自然科学版) 2013(04)
标签：定理论文; 线性森林论文; 最小度论文; 谱半径论文; 无符号拉普拉斯谱半径论文; 二部图论文; 子式论文; 边数论文; 哈密顿连通论文;