给定顶点数和边数的连通图的Q-谱半径的界

摘要：

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和,其特征值记为q1≥q2≥…≥qn.设C(n,m)是由n个顶点m条边的连通图构成的集合,这里1≤n-1≤m≤(n2).如果对于任意的G∈C(n,m)都有q1(G*)≥q1(G)成立,图G*∈C(n,m)叫做最大图.这篇文章证明了对任意给定的正整数a=m-n+1,如果n＞-1/2+a+1/2√(1+12a12a2),那么n＜ q1(G*)＜n+1,进而得到,对任意的G∈C(n,m),只要n＞-1/2+a+1/2√(1+12a12a2),就有q1(G)＜n+1.

关键词：无符号拉普拉斯矩阵、最大图、嵌套分裂图、Q-谱半径

所属期刊栏目：15

分类号：O157.5(代数、数论、组合理论)

资助基金：the National Natural Science Foundation of China 10961023

在线出版日期：2012-02-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：19-28