图的特征值和结构参数的研究

论文摘要

图谱理论是图论中非常重要的研究领域之一,它在计算机科学、信息科学、通信网络、量子化学和统计力学等方面的应用极其广泛.图谱理论的研究主要是利用矩阵论和组合矩阵论中的经典结论和方法,通过图的矩阵表示,建立起图的代数性质与拓扑结构之间的紧密联系.本文主要讨论了图的几类矩阵特征值与图的结构参数（如图的度、平均二度、传递（transmission）、直径、围长、色数、连通度等）之间的关系,进而研究图的一些性质.文章结构如下:第一章,主要介绍了图谱理论以及本文涉及问题的研究背景,而且给出了本文所用到的一些基本概念和记号.第二章,研究了连通的非正则（n,m）-图（即有n个点和m条边的图）的（无符号）拉普拉斯谱半径.首先给出了无符号拉普拉斯谱半径关于度和平均二度的上界,并刻画了对应的极图.然后,得到了（无符号）拉普拉斯谱半径关于最大、最小度的上界.最后,讨论了不同图的拉普拉斯谱半径和无符号拉普拉斯谱半径之间的关系,而且对不同图的（无符号）拉普拉斯谱半径进行了排序和比较.第三章,研究了图的Aα-矩阵的最小特征值λλn（Aααα）.令n,m,χ和qn（G）分别表示图G的点数、边数、色数和无符号拉普拉斯最小特征值.de Lima,Oliveira,de Abreu和 Nikiforov[The smallest eigenvalue of the signless Laplacian,Linear Algebra Appl.435（2011）2570-2584]提出了多个公开问题,其中两个如下:问题1:找到qn（G）=2m/n-1成立的充要条件;问题2:找到qn（G）=（1-1/χ-1）2m/n成立的充要条件.在这章中,我们首先得到了λn（Aα）（此处1/2 ≤ α ≤ 1）的一个上界并刻画了对应的极图,作为应用,完全解决了问题1.然后,当α ≠ 1/χ时给出了Nikiforov和 Rojo[A note on the positive semidefiniteness of Aα（G）,Linear Algebra Appl.519（2017）156-163]得到的 λn（Aα）≤（αχ-1）2m/（χ-1）n中等式刻画的必要条件,进而得到了问题2的必要条件.最后,考虑了λn（Aα）关于图的度、直径和围长的一些界且刻画了一些极图,改进和推广了qn（G）以及λn（Aα）的一些已有结果.第四章,考虑了图的距离（无符号拉普拉斯）谱半径.一方面,研究了循环图的距离谱半径与转发指标.通过构造任意两点间的最短路得到了几类循环图的距离谱半径以及所对应的距离矩阵的元素.然后,讨论了距离谱半径与转发指标的关系.最后,给出了几类循环图的点转发指标的确切值和边转发指标的上下界.另一方面,讨论了非传递正则图（non-transmission-regular graphs）的距离（无符号拉普拉斯）谱半径.分别用两种方法对这类图的距离（无符号拉普拉斯）谱半径与（2倍）图的最大传递之差进行了估计,并对所得结果进行了比较.而且,关于距离谱半径和图的最大传递提出了一个猜想并验证了此猜想对树是成立的.此外,利用证明中类似的方法,改进了非正则图的邻接谱半径和最大度差值的一个已有结果.第五章,对本文进行了总结,并对有待研究的问题进行了展望.

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   §1.1 研究背景
•   §1.2 基本概念与记号
• 第二章 图的（无符号）拉普拉斯谱半径
•   §2.1 引言
•   §2.2 预备知识
•   §2.3 （无符号）拉普拉斯谱半径的排序和比较
•   §2.4 本章小结
• α-矩阵的最小特征值'>第三章 图的A_α-矩阵的最小特征值
•   §3.1 引言
•   §3.2 预备知识
•   §3.3 de Lima,Oliveira,de Abreu及Nikiforov的公开问题之一
•   §3.4 de Lima,Oliveira,de Abreu及Nikiforov的公开问题之二
• α（G）矩阵的最小特征值的其他界'>  §3.5 A_α（G）矩阵的最小特征值的其他界
•   §3.6 本章小结
• 第四章 图的距离（无符号拉普拉斯）谱半径
•   §4.1 循环图的距离谱半径和转发指标
•     §4.1.1 引言
•     §4.1.2 预备知识
•     §4.1.3 循环图的距离矩阵和距离谱半径
•     §4.1.4 循环图的距离谱半径和转发指标
•   §4.2 非传递正则图的距离（无符号拉普拉斯）谱半径
•     §4.2.1 引言
•     §4.2.2 预备知识
•     §4.2.3 距离谱半径与图的最大传递
•     §4.2.4 距离无符号拉普拉斯谱半径与2倍图的最大传递
•   §4.3 本章小结
• 第五章 总结与展望
• 参考文献
• 博士学位期间的科研成果
• 致谢

文章来源

类型: 博士论文

作者: 刘淑亭

导师: 束金龙

关键词: 无符号拉普拉斯矩阵,矩阵,距离无符号拉普拉斯矩阵,最大小特征值,平均二度,直径,围长,色数,转发指标,连通度,传递

来源: 华东师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 华东师范大学

分类号: O157.5

总页数: 121

文件大小: 3478K

下载量: 89