不含三圈的k圈图的谱半径和Q−谱半径

摘要

图论是一门应用广泛的数学分支,是处理离散数学强有力的工具.在图论中,人们引入了各种矩阵,诸如图的邻接矩阵,拉普拉斯矩阵,拟(无符号)拉普拉斯矩阵,距离矩阵等.这些矩阵都与图的结构有着密切的联系.代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质(主要为矩阵的特征值性质)反映出来.
　　在上面所提到的这些矩阵中,最重要的有三个:图的邻接矩阵,拉普拉斯矩阵和拟拉普拉斯矩阵.它们的特征值都是图的同构不变量.它们的最大特征值分别称为图的谱半径,拉普拉斯谱半径和拟拉普拉斯谱半径(又称Q-谱半径).
　　对于一个给定的图类,确定该图类中图的谱半径的上界并刻画达到该上界的图,这是R.A.Brualdi和E.S.Soheid在1986年提出的关于图的谱半径的一个问题.此后,这些问题被广泛地研究,被称为Brualdi-Solheid问题,并被移植到图的拉普拉斯谱半径和拟拉普拉斯谱半径研究中,至今仍为图谱的研究热点.Nikiforov等人最近将图谱研究和极值图论相结合,提出了谱Tur′an型问题:“给定一个图F,设G是一个不含子图与图F同构的n阶图,那么图G的谱半径至多为多少?”2013年,Nikiforov等人又提出了相应的拟拉普拉斯谱Tur′an型问题:“给定一个图F,设G是一个不含子图与图F同构的n阶图,那么图G的拟拉普拉斯谱半径至多为多少?”不难看出,后两类问题均为Brualdi-Solheid问题的特殊情形.
　　k圈图是边数等于顶点数加k-1的简单连通图,当k=0,1,2,3时,分别为树,单圈图,双圈图和三圈图.任意两个圈至多有一个公共顶点的简单连通图称为无交图.本文首先研究不含三圈的k圈图的拟拉普拉斯谱半径,确定了不含三圈的k圈图的拟拉普拉斯谱半径的上界,并刻画了达到上界的极图,同时还确定了拟拉普拉斯谱半径排在前五位的不含三圈的单圈图,排在前八位的不含三圈的双圈图,排在前九位的不含三圈的三圈图,排在前五位的不含三圈的无交k圈图.其次,我们还研究了不含三圈的双圈图的谱半径,确定了不含三圈的双圈图谱半径的第一和第二大值,并刻画了相应的极图.

目录

封面

声明

中文摘要

英文摘要

目录

第一章 引言

第二章 预备知识

§ 2.1 概念和记号

§ 2.2 本文用到的一些引理

第三章 不含三圈的k圈图的拟拉普拉斯谱半径

§ 3.1 主要引理

§ 3.2 不含三圈的k圈图的拟拉普拉斯谱半径的上界

§ 3.3 不含三圈的单圈图按拟拉普拉斯谱半径的排序

§ 3.4 不含三圈的双圈图按拟拉普拉斯谱半径的排序

§ 3.5 不含三圈的三圈图按拟拉普拉斯谱半径的排序

§ 3.6 不含三圈的无交k圈图按拟拉普拉斯谱半径的排序

第四章 不含三圈的双圈图按谱半径的排序

§ 4.1 不含三圈的∞型双圈图谱半径的上界

§ 4.2 不含三圈的θ型双圈图谱半径的上界

§ 4.3 不含三圈的θ型双圈图谱半径的第二大值

§ 4.4 不含三圈的双圈图按谱半径的排序

参考文献

致谢

个 人 简 介