路矩陣相關(guān)譜半徑和路譜展的界及其應(yīng)用

盧鵬麗， 欒睿

(蘭州理工大學(xué) 計算機(jī)與通信學(xué)院，甘肅 蘭州 730050)

1 基本概念和主要引理

引理2[14]n階連通圖G只有2個不同的路特征值當(dāng)且僅當(dāng)G是k-連通且k-正則圖，2≤k≤n-1。

引理3[15]設(shè)Q為對應(yīng)于方陣A的等價劃分的商矩陣，則A的譜包含Q的譜。

2 圖的路譜半徑和路無符號拉普拉斯譜半徑的界

等式成立當(dāng)且僅當(dāng)G為路傳遞正則圖。

定理3若G為簡單連通圖，則：

等式成立當(dāng)且僅當(dāng)G為路傳遞正則圖。

證明：因為PQ(G)=TrP(G)+P(G)，通過簡單計算可得

則

rvi((PQ(G))2)=rvi((TrP)2+TrPP+PTrP+P2)=

rvi(TrP(TrP+P))+rvi(PTrP)+rvi(P2)=

定理4若G為簡單連通圖，則：

等式成立當(dāng)且僅當(dāng)G為路傳遞正則圖。

證明：證明過程同定理3。

(1)

等式成立當(dāng)且僅當(dāng)G為路傳遞正則圖。

3 路譜展的下界

定理6設(shè)圖G為n階連通圖，則：

(2)

等式成立當(dāng)且僅當(dāng)G為k-連通且k-正則圖。

當(dāng)且僅當(dāng)ρ2=ρ3=…=ρn時式(2)取等，即當(dāng)且僅當(dāng)G有2個完全不同的路特征值。利用引理2，可以得出G為k-連通且k-正則圖。反之，若G為k-連通且k-正則圖，可通過直接計算可證。該定理得證。

定理7設(shè)圖G為n階連通圖，則：

等式成立當(dāng)且僅當(dāng)G為k-連通且k-正則圖。

證明：因為

(3)

當(dāng)且僅當(dāng)ρ2=ρ3=…=ρn時式(3)取等，即當(dāng)且僅當(dāng)G有2個完全不同的路特征值。利用引理2，可以得出G是k-連通且k-正則圖。反之，若G為k-連通且k-正則圖，可通過直接計算可證。該定理得證。

推論1設(shè)圖G為n階連通圖，其路Wiener指數(shù)為PW(G)，則：

PS(G)≥

等式成立當(dāng)且僅當(dāng)G為k-連通且k-正則圖。

證明：根據(jù)定理1和定理7可證。

定理8設(shè)圖G為n階連通圖，則：

4 完全r-部圖的路譜和路(無符號)拉普拉斯譜

SpecP(Kp1,p2,…,pr)=((p1-n)p1-1,(p2-n)p2-1,…,

(pr-n)pr-1,1,2,…,n)

的特征值。

證明：給頂點集V(Kp1,p2,…,pr)一個劃分π:V(Kp1,p2,…,pr)=V1∪V2∪…∪Vr，其中Vi為第i部中的頂點，則完全r-部圖Kp1,p2,…,pr的路矩陣P(Kp1,p2,…,pr)的分塊矩陣表示為：

則這個矩陣的n-r個特征值為：(p1-n)p1-1,(p2-n)p2-1,…,(pr-n)pr-1。因為π為圖Kp1,p2,…,pr的路等價劃分，所以其對應(yīng)的商矩陣Q3由式(4)給出，計算det(xI-Q3)，可得Q3的特征值，由引理3可知，即為P(Kp1,p2,…,pr)的剩余r個特征值。

推論2令Kp,p,…,p為特殊的完全r-部圖，其中r≥2，n=rp，則 SpecP(Kp,p,…,p)=((p-n)n-1,((n-p)(n-1))1)，PE(Kp,p,…,p)=2(n-p)(n-1)。

證明：根據(jù)定理9可證。

其中ζ1,ζ2,…,ζr為矩陣

的特征值。

證明：

其中：

(n-p3)Jp3×p3，…，

證明過程同定理9。

推論3令Kp,p,…,p為特殊的完全r-部圖，其中r≥2，n=rp，則 SpecPL(Kp,p,…,p)=((n(n-p))n-1,0)，PLE(Kp,p,…,p)=2(n-p) ·(n-1)。

證明：根據(jù)定理10可證。

其中ξ1,ξ2,…,ξr為矩陣

的特征值。

其中：

?

證明：

其中：

?

證明過程同定理9。

推論4令Kp,p,…,p為特殊的完全r-部圖，其中r≥2，n=rp，則 SpecPQ(Kp,p,…,p)=(((n-2)(n-p))n-1,(2(n-1)(n-p))1)，PSLE(Kp,p,…,p)=2(n-p)(n-1)。

證明：根據(jù)定理11可證。

5 結(jié)論

1)得到了任意圖的路譜半徑和路(無符號)拉普拉斯譜半徑的界。

2)定義了路譜展的概念并得到其下界。

3)計算了完全r-部圖的路譜和路(無符號)拉普拉斯譜及其能量，拓寬了路譜的研究范圍。