单圈图的最小无号Laplacian谱展

2013-08-16 08:27游志福
关键词:单圈特征值顶点

游志福

(广东技术师范学院计算机科学学院,广东广州510665)

设G为n阶简单图,其顶点集V(G)={v1,v2,…,vn}.对于点u,用N(u)表示u的邻点集,d(u)是点u的度.图G的最大度和最小度分别用Δ和δ表示.设G-v是由G通过删去点v和关联v的所有边所成的图.图G的邻接矩阵,记为A(G)=(aij)n×n,是n阶方阵,其中当顶点 vi和vj在G中相邻时aij=1,否则aij=0.矩阵A(G)的特征多项式也称为图G的特征多项式:

其中I为n阶单位阵.由于A(G)是实对称矩阵,所以其n个特征值都是实数,记为λ1(G),λ2(G),…,λn(G),在不引起混淆的情况下简记为 λ1,λ2,…,λn.不失一般性设 λ1≥λ2≥… ≥λn,并称它们为图G的特征值.G的特征值的全体称为图G的谱.

图的度矩阵 D=diag(d1,d2,…,dn)是图 G 的由点度构成的对角矩阵.图G的Laplacian矩阵定义为L(G)=D(G)-A(G).矩阵L(G)的特征多项式也称为图G的Laplacian特征多项式:

矩阵L是实对称、半正定的奇异矩阵,记其特征值为 μ1≥μ2≥…≥μn-1≥μn=0.

图 G 的谱展[1]定义为:S(G)=λ1- λn.图 G 的Laplacian 谱展[2]定义为:LS(G)=μ1-μn-1.

矩阵Q(G)=D(G)+A(G)称为无号Laplacian矩阵,其特征多项式也称为图G的无号Laplacian特征多项式:

设其特征值为q1≥q2≥…≥qn-1≥qn≥0.

类似于邻接和 Laplacian谱展,图 G的无号Laplacian 谱展[3-4]定义为 QS(G)=q1-qn.

OLIVEIRA等[4]给出:Pn在 n阶树图中取得最小无号Laplacian谱展.本文刻画了给定阶数的连通单圈图无号Laplacian谱展的下界及极图.

简记无号Laplacian矩阵的特征值为Q-特征值.引理1说明了图G的去边子图的Q-特征值内插图G的Q-特征值.

引理1[5]设 e 是图 G 的一条边,q1,q2,…,qn(q1≥…≥qn)和 s1,s2,…,sn(s1≥…≥sn)分别是 G和G-e的Q-特征值,则

引理2 设G是一个n阶图且v是一个悬挂点,则 QS(G)≥QS(G-v).

证明 对于悬挂点v,设G和G-v的Q-特征值分别为q1≥…≥qn和s1≥…≥sn-1.注意到s1,…,sn-1和sn=0是 G-e的 Q-特征值,其中 e是关联点v的边.由引理1,有

从而 QS(G)=q1-qn≥s1-sn-1=QS(G-v). □

引理3[6-7]设G是一个至少有一边的图,则q1≥μ1≥Δ+1.若G是连通的,第1个等号成立当且仅当G是二部图,第2个等号成立当且仅当Δ =n-1.

Ea,b表示通过合并圈Ca中的一顶点和Pb+1的一个端点所成的a+b阶单圈图.文献[5]指出

根据文献[8]中一个关于最大Laplacian特征值的下界,YOU 和 LIU[9]获得了:

下面引理对本文主要结果有重要意义,其中Ea,b如上所定义.

引理4 设k≥3是一个任意正整数,则

证明 对于k≥30,由式(1)和引理3,有

当3≤k≤29,由直接计算可得表1.

表1 Ek,1(3≤k≤29)的最大和最小无号Laplacian特征值Table 1 The largest and smallest signless Laplacian eigenvalues of Ek,1(3≤k≤29)

如果3≤k≤29,由表1,有 QS(Ek,1)>4.综上可知结论成立.

引理5[3]如果G是一个连通图且最大度为Δ,最小度为 δ,则QS(G)>Δ +1-δ.

定理1 设G是一个n阶单圈图且G≇Cn,则QS(G)>4.

证明 注意到 G≇Cn,则 δ=1.若 Δ≥4,由引理5,有 QS(G)>4+1-1=4.

下设G是一个n阶单圈图且Δ=3.令v是一个悬挂点.由引理2,有QS(G)≥QS(G-v).若G-v≅Cn-1,即 G≅En-1,1,由引理 4,有 QS(G)> 4.若 G≇En-1,1,通过逐渐删去图G的悬挂点,则G可以转化为 Ek,1(k≤n-2)且

因此,定理1的结论成立. □

引理6[10]设 q1是连通图 G的最大 Q-特征值,则q1=4当且仅当G是一个圈或者K1,3.

引理7[10]连通图的最小无号Laplacian特征值等于0当且仅当此图是二部图.

由引理6和引理7,有:

命题1 设Cn是n阶圈图,则QS(Cn)≤4且等号成立当且仅当n是偶数.

结合定理1和命题1,有:

定理2 设G是一个n阶单圈图,则QS(G)≥QS(Cn).等号成立当且仅当G≅Cn.

[1]GREGORY D A,HERSHKOWITZ D,KIRKLAND S J.The spread of the spectrum of a graph[J].Linear Algebra Appl,2001,332-334:23-35.

[2]FAN Y Z,XU J,WANG Y,et al.The Laplacian spread of a tree[J].Discrete Math Theor,2008,10:79-86.

[3]LIU M H,LIU B L.The signless Laplacian spread[J].Linear Algebra Appl,2010,432:505-514.

[4]OLIVEIRA C S,LIMA L S,ABREU N M M,et al.Bounds on the Q-spread of a graph[J].Linear Algebra Appl,2010,432:2342-2351.

[5]CVETKOVI'C D,ROWLINSON P,SIMI'C SK.Eigenvalue bounds for the signless Laplacian[J].Publ Inst Math(Beograd),2007,81(95):11-27.

[6]MERRISR.Laplacianmatrices of graphs:A survey[J].Linear Algebra Appl,1994,197-198:143-176.

[7]PAN Y L.Sharp upper bounds for the Laplacian graph eigenvalues[J].Linear Algebra Appl,2002,355:287-295.

[8]DAS K C.The largest two Laplacian eigenvalues of a graph[J].Linear Multilinear A,2004,52:441-460.

[9]YOU Z F,LIU B L.The minimun Laplacian spread of unicyclic graphs[J].Linear Algebra Appl,2010,432:499-504.

[10]CVETKOVI'C D,ROWLINSON P,SIMI'C SK.Signless Laplacians of finite graphs[J].Linear Algebra Appl,2007,423:155-171.

猜你喜欢
单圈特征值顶点
一类单圈图的最大独立集的交
过非等腰锐角三角形顶点和垂心的圆的性质及应用(下)
一类带强制位势的p-Laplace特征值问题
单圈图关联矩阵的特征值
关于顶点染色的一个猜想
H型群上一类散度形算子的特征值估计
基于商奇异值分解的一类二次特征值反问题
具有最多与最少连通子图的单圈图
剩余类环Z/(pn)上若干类单圈多项式构造
数学问答