單圈圖的最小無號Laplacian譜展

游志福

(廣東技術(shù)師范學院計算機科學學院，廣東廣州510665)

設(shè)G為n階簡單圖，其頂點集V(G)={v1，v2，…，vn}．對于點u，用N(u)表示u的鄰點集，d(u)是點u的度．圖G的最大度和最小度分別用Δ和δ表示．設(shè)G-v是由G通過刪去點v和關(guān)聯(lián)v的所有邊所成的圖．圖G的鄰接矩陣，記為A(G)=(aij)n×n，是n階方陣，其中當頂點 vi和vj在G中相鄰時aij=1，否則aij=0．矩陣A(G)的特征多項式也稱為圖G的特征多項式:

其中I為n階單位陣．由于A(G)是實對稱矩陣，所以其n個特征值都是實數(shù)，記為λ1(G)，λ2(G)，…，λn(G)，在不引起混淆的情況下簡記為 λ1，λ2，…，λn．不失一般性設(shè) λ1≥λ2≥… ≥λn，并稱它們?yōu)閳DG的特征值．G的特征值的全體稱為圖G的譜．

圖的度矩陣 D=diag(d1，d2，…，dn)是圖 G 的由點度構(gòu)成的對角矩陣．圖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特征多項式:

設(shè)其特征值為q1≥q2≥…≥qn-1≥qn≥0．

類似于鄰接和 Laplacian譜展，圖 G的無號Laplacian 譜展［3-4］定義為 QS(G)=q1-qn．

OLIVEIRA等［4］給出:Pn在 n階樹圖中取得最小無號Laplacian譜展．本文刻畫了給定階數(shù)的連通單圈圖無號Laplacian譜展的下界及極圖．

簡記無號Laplacian矩陣的特征值為Q-特征值．引理1說明了圖G的去邊子圖的Q-特征值內(nèi)插圖G的Q-特征值．

引理1［5］設(shè) e 是圖 G 的一條邊，q1，q2，…，qn(q1≥…≥qn)和 s1，s2，…，sn(s1≥…≥sn)分別是 G和G-e的Q-特征值，則

引理2 設(shè)G是一個n階圖且v是一個懸掛點，則 QS(G)≥QS(G-v)．

證明 對于懸掛點v，設(shè)G和G-v的Q-特征值分別為q1≥…≥qn和s1≥…≥sn-1．注意到s1，…，sn-1和sn=0是 G-e的 Q-特征值，其中 e是關(guān)聯(lián)點v的邊．由引理1，有

從而 QS(G)=q1-qn≥s1-sn-1=QS(G-v)． □

引理3［6-7］設(shè)G是一個至少有一邊的圖，則q1≥μ1≥Δ+1．若G是連通的，第1個等號成立當且僅當G是二部圖，第2個等號成立當且僅當Δ =n-1．

Ea，b表示通過合并圈Ca中的一頂點和Pb+1的一個端點所成的a+b階單圈圖．文獻［5］指出

根據(jù)文獻［8］中一個關(guān)于最大Laplacian特征值的下界，YOU 和 LIU［9］獲得了:

下面引理對本文主要結(jié)果有重要意義，其中Ea，b如上所定義．

引理4 設(shè)k≥3是一個任意正整數(shù)，則

證明 對于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．綜上可知結(jié)論成立．

引理5［3］如果G是一個連通圖且最大度為Δ，最小度為 δ，則QS(G)＞Δ +1-δ．

定理1 設(shè)G是一個n階單圈圖且G?Cn，則QS(G)＞4．

證明 注意到 G?Cn，則 δ=1．若 Δ≥4，由引理5，有 QS(G)＞4+1-1=4．

下設(shè)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可以轉(zhuǎn)化為 Ek，1(k≤n-2)且

因此，定理1的結(jié)論成立． □

引理6［10］設(shè) q1是連通圖 G的最大 Q-特征值，則q1=4當且僅當G是一個圈或者K1，3．

引理7［10］連通圖的最小無號Laplacian特征值等于0當且僅當此圖是二部圖．

由引理6和引理7，有:

命題1 設(shè)Cn是n階圈圖，則QS(Cn)≤4且等號成立當且僅當n是偶數(shù)．

結(jié)合定理1和命題1，有:

定理2 設(shè)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．