代数图论中的若干问题

论文摘要

代数图论是图论的一个重要分支,其主要是运用代数的方法和结果来研究图论中的问题.图的谱论是代数图论研究的重要课题之一,它主要通过图的一些矩阵表示如：邻接矩阵、拉普拉斯矩阵及无符号拉普拉斯矩阵等,运用矩阵理论来研究这些矩阵的代数性质,进而得出图的拓扑结构性质等.由于图的许多不变量都包含在某些多项式里面,所以在图论中,经常使用多项式理论来研究图的性质.运用多项式理论来研究图的性质是代数图论的另一个重要课题.图的谱论和图的多项式理论都有着重要的理论价值和广泛的应用背景.关于这两个课题,本文主要考虑了两类问题,一类是给定图类的谱论极值及与图谱相关的拓扑指标的极值问题；另一类是图的独立多项式的单峰型问题.具体内容如下：第一部分研究了给定割点个数为κ的n阶连通图(分别地,二部图)的无符号拉普拉斯谱半径的极值问题.分别得到了无符号拉普拉斯谱半径的上界和刻画了达到上界所对应的极值图.类似地,可以重新证明Berman和Zhang的关于这类图的谱半径极值的结果和扩大Fan和Wang的关于这类图的最小特征值极值的结果.第二部分考虑了给定割边个数(分别地,最大度)的n阶连通图的最小特征值的极值问题.作者分别得到了最小特征值的下界,而且刻画了对应的极值图.第三部分研究了给定连通度(分别地,色数和匹配数)的n阶连通图的拟拉普拉斯能量和拉普拉斯Estrada指标的极值问题.作者分别得到了拟拉普拉斯能量和拉普拉斯Estrada指标的上界,而且确定了达到上界对应的极值图.第四部分给出了某类图的独立多项式的因式分解.作为应用,一方面证明了所有的vertebrated图和firecracker图的独立多项式都是对数凹和单峰的,这就统一地证明了Levit和Mandrescu以及朱志峰的结果,特别地肯定了朱志峰的一个猜想,进一步也否定了Levit和Mandrescu的一个关于centipede图的独立多项式的峰点位置的猜想.另一方面也推广了Chudnovsky和Seymour的结果.使用类似的方法,作者也肯定了Levit和Mandrescu的一个关于独立多项式的对数凹性的猜想.最后,这样的方法也适用于图的其他多项式.

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 基本概念和记号
• 1.2 关于图的谱论的国内外发展概况
• 1.3 关于图论中单峰型问题的国内外发展概况
• 1.4 本文主要工作简介
• 2 图的无符号拉普拉斯谱半径
• 2.1 引言
• 2.2 给定割点个数的连通图的无符号拉普拉斯谱半径
• 2.3 给定割点个数的连通二部图的无符号拉普拉斯谱半径
• 2.4 给定割点个数的连通图的最小特征值
• 2.5 本章小结
• 3 图的最小特征值的下界
• 3.1 引言
• 3.2 给定割边个数的连通图的最小特征值
• 3.3 给定最大度的连通图的最小特征值
• 3.4 本章小结
• 4 图的拟拉普拉斯能量及拉普拉斯Estrada指标与图的不变量
• 4.1 引言
• 4.2 图的连通度与拟拉普拉斯能量及拉普拉斯Estrada指标
• 4.3 图的色数与拟拉普拉斯能量及拉普拉斯Estrada指标
• 4.4 图的匹配数与拉普拉斯Estrada指标
• 4.5 本章小结
• 5 图的独立多项式的单峰性
• 5.1 引言
• 5.2 引理和主要结论
• 5.2.1 Vertebrated图和Firecracker图
• 5.2.2 无爪图
• 5.2.3 圈连图
• 5.3 Levit和Mandrescu的一个猜想
• 5.4 进一步讨论
• 5.5 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表论文及获奖情况
• 致谢
• 作者简介