图的哈密顿性质、β-亏损性和超欧拉性研究

来源 :华南理工大学 | 被引量 : 0次 | 上传用户:tianshanfeiren
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论(Graph Theory)是数学的一个重要分支,它以图为研究对象,在交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域有广泛的应用.图论的哈密顿圈问题(Hamilton circuit problem)是图论中著名的难题之一,吸引了众多图论工作者的关注与研究.判断一个图具有哈密顿性质的充分条件主要包含以下两类:一类是从参数的角度刻画,常用的有独立数、最小度、度序列等;另一类是从结构图论的角度,如考虑禁用某些特定的子图.在参数角度研究中,早期工作大多都是从边数条件、度条件和邻域条件等出发来刻画图的哈密顿性质.2010年,Fiedler和Nikiforov首先给出了邻接矩阵谱半径与图的哈密顿性的关系,建立了图谱理论与哈密顿性质之间的联系.图谱理论主要是利用代数理论和方法,结合图论和组合数学的理论,研究矩阵的特征值以及与图的其它不变量之间的关系,它是当代图论、组合矩阵和代数组合共同关注的重要研究课题,在量子力学、理论物理、化学等中有着广泛的应用.图谱理论与哈密顿性质关系的建立,受到研究者的广泛关注及研究.本博士论文研究图的哈密顿性质、β-亏损性和超欧拉性,主要结果如下:1)得到了一个图具有哈密顿性质的几个充分条件.首先,我们利用特征向量理论、Rayleigh商和不等式理论改进了 Nikiforov的2016年的一个结果,即关于给定最小度的n阶图为可迹图的一个谱半径充分条件;同时还获得了给定阶数和最小度的平衡二部图为可迹图的新的谱半径条件.接着,利用Erdos将最小度作为参数的思想,得到了给定阶数和最小度的图为哈密顿连通图的一个新的边数条件.最后,利用该边数条件、特征向量理论、Kelmans变换、Rayleigh商和不等式理论给出了一个给定阶数和最小度的图为哈密顿连通图的一个新的谱充分条件.2)得到了一个图具有β-亏损性的几个充分条件.令M为图G的最大匹配,图G中,未被M匹配的顶点的个数称为图G的亏损数,记为def(G).令β是一个非负整数,当def(G)≤β时,称图G是β-亏损的.在本文中,我们利用范引理、Berge最大匹配定理以及Kouider定理,首次获得了图具有β-亏损性的Chvatal-Erdos类型独立数条件.接着,利用研究哈密顿性质时所积累的方法,首次获得了图具有β-亏损性的最小度条件、度和条件以及度序列条件.最后,利用我们所得的Chvat al-Erdos类型独立数条件和最小度条件给出了图具有β-亏损性的两个新的谱充分条件.3)得到了一个图具有超欧拉性的几个充分条件.1991年,Catlin和Chen利用Catlin约化方法,分别给出了 2-边连通图和3-边连通图为超欧拉图的一个边数条件.在本文中,我们利用研究哈密顿性质的最小度参数思想、Catlin约化方法及极值图论的思想,改进了上述结果中的两个边数条件,从而得到了给定边连通度和最小度的图为超欧拉图的几个新的充分条件.接着,利用我们所得的边数条件和Fourier-Budan定理,以及研究哈密顿性质谱条件时所积累的方法,首次获得了一个图具有超欧拉性的谱半径充分条件和无符号拉普拉斯谱半径充分条件。
其他文献
气溶胶广泛分布在大气中,其来源广泛,对于人类的呼吸健康和生产、生活以及地球的辐射传输起着至关重要的作用。特别是随着工业的迅速发展和人口的快速增加,使得人类活动产生
随着生产生活和学术研究中数据的规模和维度越来越大,如何在尽可能减少计算量的前提下进行精确的统计推断,已经成为了一个值得关注的重要研究方向。应用除偏方估计对高维数据
稀土掺杂纳米材料已广泛应用在荧光显示、激光、信息传输等领域,尤其是在生物成像方面具有很大的应用前景。成像技术能够直观显示活体动物体内的细胞活动和病灶演变,是生物检
地表温度和土壤湿度是区域和全球尺度上陆地表层生态系统中两个非常重要的物理量,两者的精确获取对与人类生产生活密切相关的诸多领域,如农业、气候等具有至关重要的作用。遥
随着信息技术和网络的普及、应用与进步,我国交通运输行业的信息化建设得到了飞速发展。智能交通系统对信息资源带来网络化、系统化及共享化的同时,也面临着越来越严峻的安全
过去四十多年来,我国在扶贫领域取得了突出成绩。自党的十八大以来,脱贫攻坚就被纳入“四个全面”战略布局,党中央、国务院以前所未有的力度推进,取得举世瞩目的伟大成就;继
分子间电子能量转移(Electronic energy transfer,EET)是一种普遍存在的光物理过程,深入理解供体-受体系统中的EET机制对于在光合作用和光伏发电中设计构造光收集系统非常重
全球范围内与W成矿密切相关的岩体,主要有S型、A型和I型花岗质岩石,与高分异还原型S型或I型花岗质岩石及与A型花岗岩密切相关的W、Sn矿床的成岩、成矿作用研究较深入,与弱分
地表覆被信息的空间格局及时空动态变化对研究全球及区域变化、可持续发展和生态保护等至关重要;其中耕地(水田、旱地)覆被要素的种植信息及演变格局对粮食安全风险评估、生
本文针对二元边坡开挖支护过程中结构受力变形特征复杂和容易造成失稳破坏的问题,以山区公路挖方路段土-岩二元边坡为研究对象,开展桩锚加固二元边坡稳定性评估和稳态渗流分