无符号拉普拉斯特征值的界

【摘要】：图论是一个重要的数学分支,在实际生活中有着诸多重要的应用.为了用代数方法来研究图,人们引进了各种矩阵,如邻接矩阵、距离矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵等,这些矩阵在同构意义下都是相似的.因此,这些矩阵的性质和图本身的结构有着密切的联系.本文主要是对图的无符号拉普拉斯谱特征值(Q-特征值)进行了研究,分为四章.第一章,我们给出了图相关的定义、符号和记号,综述了图的无符号拉普拉斯矩阵的研究的历史及现状,并列出了本人的主要研究成果.第二章,我们给出了图论中常用的矩阵知识以及后文证明所需要的一些引理.第三章,我们研究了删点集对图的无符号拉普拉斯谱(Q-谱)的影响,给出了删点集插值定理.进一步,得到了一个下界()1(1,2,,)i iq G≥d-i+i=Ln,其中qi(G)为n阶图G的第i大Q-特征值,id为第i大顶点度.另外,给出了qi(G)=di-1(i=2,3,…,k)成立的一个充分条件以及等式成立的必要条件等.第四章,我们研究了一类图的最小无符号拉普拉斯特征值,即最小Q-特征值.它的最小Q-特征值的可达上界为1,并构造了最小Q-特征值为1的一类图.另外,给出了利用1KH∨的最小Q-特征值来判断简单图H没有完美匹配的一个方法.最后,构造了最小Q-特征值为任意给定的正整数的一类图以及为δ-1的一类图.
【关键词】：图 特征值 无符号拉普拉斯矩阵
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：O157.5