论文部分内容阅读
图论(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定理,以及研究哈密顿性质谱条件时所积累的方法,首次获得了一个图具有超欧拉性的谱半径充分条件和无符号拉普拉斯谱半径充分条件。