关于图的特征值的几个问题的研究

1、yiT论女第表站家关于图的特征值的几个问题的研究【摘要】：图谱理论是图论研究的一个非常活跃而又重要的研究领域，它在量子化学、统计力学、计算机科学、通信网络以及信息科学中均 有着广泛的应用图谱的研究主要是利用线性代数、矩阵论等成熟的 理论和技巧，巧妙地把图的一些基本结构性质和它的参数联系在一起,并找出它们之间的内在关系.在图谱理论中，为了研究图的性质，人们 引入了各种各样的矩阵常见的有图 G 的邻接矩阵 A(G)、拉普拉斯矩 阵 L(G)、关联矩阵 M(G)、距离矩阵 D*(G)以及无符号拉普拉斯矩阵 Q(G)等等.这些矩阵都与图的结构都有着密切的联系图谱理论的一个 主要问题就是研究图的性质能否

2、以及如何由这些矩阵的代数性质(主要是指矩阵的特征值性质)反映出来尽管这些定义不同的矩阵有着各 种丰富的形式，但是他们的特征多项式(或者说谱)之间却很可能是互 相关联的.在20中 Qragos 列举说明了在二部图中，无符号拉普拉斯谱 和拉普拉斯谱相同同时我们知道，图的拉普拉斯矩阵的非零特征值和 它的线图的邻接特征值也有着密切的关系这样，通过二部图就可以把 它们紧密地联系在一起又例如,令那么,邻接矩阵的特征多项式可以 表示为 FG(x,0),拉普拉斯矩阵的特征多项式可以表示为 (1)nFG(x,1),无符号拉普拉斯矩阵的特征多项式可以表示为 FG(x, 1)等等尽管如此，由于它们都有自己独特的应用

3、背景和实际 价值,我们还是很有必要对这些不同的矩阵和谱展开针对性的研究的.在上面所提及的矩阵中，最重要的两个就是图的邻接矩阵和拉普拉斯矩阵本文研究的主要问题在三个方面：(1)简单连通无向图的拉普拉 斯谱及其极限点；(2)有向图的邻接谱半径；无符号拉普拉斯特征值的极限点和谱半径我们试图建立它们与图的结构参数之间的一些 关系.具体内容如下：(一)在第一章中，我们首先回顾了图论的整个发 展过程，接着介绍了 -些常见的谱理论研究中相关的问题的代数图论背 景和研究技巧在第二小节中,我们给出了一般的图论中的一些基本概 念和记号.文章中一些特殊的定义未在此节中出现的，我们将在后面的 相关章节中具体介绍在第三

4、小节中，我们简单介绍了和本文相关极限 点以及谱半径等问题的一一些进展及最新结果(二)在第二章中的第一小节中，我们首先通过找到一个图序列 Gn,证明它的第三大拉普拉斯特征值极限点存在，并且满足而后，我们证明 1 和上式中 1.5550 分 别是第三大拉普拉斯特征值的第一小和第二小极限点在第二小节中，对同定的 b,假设 13(b)和 I 3(分别是方程( 口 2(卩一 1)2(Q)=0 和 b (卩(卩一 1)2( g3(卩1)( 2)=0 的第二大根.我们证明了 13(b)和 I 3(b)(b=0,1,都是第三大拉普拉斯特征值极限点接着,我们 确定了 13(b)和 I 3(1 以及 2 是第三大

5、拉普拉斯特征值在区间(0,2内的 所有极限点，并且证明了 I 3(b)I3(b)I 3 从而对(0,2中的极限点按照大小进行排序最后，在第三小节中，我们通过构造图类，证明任何一 个正整数 k 都是第三大拉普拉斯特征值的极限点.(三)在第三章中，我 们首先在第一节里刻画了所有满足其第二大拉普拉斯特征值卩2(G)1的连通图 G 其中 1=3.2470 是三次方程 卩 35 卩 2+6 0 的第一大根. 在此基础上，我们通过对图的拉普拉斯特征多项式和特征值的讨论，在第二小节里求出所有小于等于 1=3.2470的第二大拉普拉斯特征值的 极限点.（四）在第四章中，我们首先在第一小节中考虑在有向图的一些

6、移接变形后谱半径的变化情况，然后给出团数和围长等固定的有向图 中谱半径取到最小时的极图以及强连通图的最小和第二小谱半径最后,我们求出了点连通度给定的强连通有向图的最大谱半径（五）在第五章中，我们首先主要以顶点度 di 和图的边数 m 为参数，通过矩阵相似 变换,讨论了弱并接（weakjoin）图的谱半径的上界，并刻画了达到这个 上界的极图谱半径的上界的准确估计，对于考虑图的最大特征值的极 限点的存在性有至关重要的作用接着，我们根据第二章和第三章的内 容,给出了无符号拉普拉斯特征值的一些极限点的存在情况.【关键词】：邻接矩阵拉普拉斯矩阵特征多项式极限点禁用子图有向图邻接 谱半径无符号拉普拉斯谱半

7、径直径周长【学位授予单位】：华东师范大学【学位级别】：博士【学位授予年份】：2011【分类号】：0157.5【目录】：摘要 6-9Abstract9-13 第一章绪论 13-271.1 研究背景与发展13-171.2 基本概念与记号 17-211.3 本文的主要问题及其进展 21-27 第 二章第三大拉普拉斯特征值的极限点 27-482.1 第三大拉普拉斯特征C 易发表用yiT论女第表匸凉值的第一及第二小极限点 27-372.2 第三大拉普拉斯特征值的第K小极限点 37-462.3 第三大拉普拉斯特征值的整数极限点46-48 第三章第二大拉普拉斯特征值的极限点48-633.1 刻画 卩_2(G)兵的连通图48-603.2卩_2(G)于等于 I 的极限点 60-63 第四章有向图的谱半径 63-764.1关于有向图的一些移接变形 63-664.2 有向图的最小及第二小 谱半径66-724.3 点连通度给定的强连通有向图的最大谱半径72-76 第