廣義并接圖的無符號(hào)拉普拉斯譜半徑

吳雅容

(上海海事大學(xué) 文理學(xué)院， 上海 201306)

1 相關(guān)定義與引理

1.1 定義

設(shè)圖為G= (V,E)，其中:V=V(G) = {v1,v2,…,vn} 為頂點(diǎn)集, |V| =n為圖G的階數(shù);E=E(G) = {e1,e2,…,em}為邊集, |E| =m為圖G的邊數(shù). 若邊e= (u,v) =uv的兩個(gè)端點(diǎn)分別為頂點(diǎn)u和v, 則稱頂點(diǎn)u與v相鄰接, 記為u～v; 否則稱它們不相鄰, 記為uv. 若邊e= (u,v)∈E, 則稱頂點(diǎn)u或v與邊e關(guān)聯(lián). 與頂點(diǎn)v關(guān)聯(lián)的邊的個(gè)數(shù)稱為頂點(diǎn)v的度(或頂點(diǎn)v的次), 記作deg(v)=dv. 圖G中最大、最小的頂點(diǎn)的度分別記為 △(G) 和δ(G). 用NG(v) 表示頂點(diǎn)v在圖G中所有相鄰的頂點(diǎn)所組成的集合. 若圖G只有一個(gè)分支, 則稱圖G是連通的.

圖G的鄰接矩陣記為A(G) = (aij)n×n, 是一個(gè)n階的(0,1)方陣, 其定義為

稱矩陣Q(G) =D(G) +A(G) 為圖G的無符號(hào)拉普拉斯矩陣. 這里,D(G)=diag (d1,d2,…，dn) 是以圖G的相應(yīng)頂點(diǎn)的度為元素的對(duì)角矩陣. 稱det (qI-Q(G)) 為圖G的無符號(hào)拉普拉斯特征多項(xiàng)式. 顯然,Q(G)是一個(gè)實(shí)非負(fù)對(duì)稱矩陣, 其n個(gè)特征值從大到小記為q1(G)≥q2(G)≥…≥qn(G)≥0， 其中：最大特征值q1(G) 稱為圖G的無符號(hào)拉普拉斯譜半徑, 簡記為q(G). 非負(fù)實(shí)矩陣Q(G)的對(duì)應(yīng)于最大特征值q(G) 的一個(gè)單位特征向量X稱為圖G的無符號(hào)拉普拉斯主特征向量. 有

假設(shè)圖G1和G2均為簡單連通圖. 如果圖G1中的每個(gè)頂點(diǎn)都與G2中一樣多的頂點(diǎn)相鄰, 并且圖G2中的每個(gè)頂點(diǎn)也都與G1中一樣多的頂點(diǎn)相鄰, 那么稱圖G1廣義并接圖G2, 或者圖G2廣義并接圖G1. 由此得到的廣義并接圖記為G=G1▽G2. 特別地, 當(dāng)圖G1中的每個(gè)頂點(diǎn)都與G2中的s個(gè)頂點(diǎn)相鄰, 而圖G2中的每個(gè)頂點(diǎn)都與G1中的t個(gè)頂點(diǎn)相鄰時(shí), 把G1▽G2記為G=G1▽G2(s,t).

文中所有的符號(hào)和術(shù)語都是標(biāo)準(zhǔn)的, 可以參考文獻(xiàn)[8].

1.2 引理

引理1假設(shè)A是一個(gè)不可約的非負(fù)矩陣,ρ(A) 是A的最大特征值. 如果A的行和分別為s1,s2,…,sn, 則

當(dāng)且僅當(dāng)s1=s2=… =sn,等式成立.[9]

2 主要結(jié)果

定理1假設(shè)圖G是一個(gè)n階的簡單連通圖, 那么2δ≤q(G) ≤ 2△, 當(dāng)且僅當(dāng)G是一個(gè)正則圖時(shí)，等式成立.

證明：根據(jù)Q(G) 的定義, 顯然矩陣中第i行的行和si等于頂點(diǎn)vi的度di的兩倍. 根據(jù)引理1, 則有 2δ≤q(G) ≤ 2△. 證畢.

q(G)≤

(1)

當(dāng)且僅當(dāng)G1和G2均為正則圖時(shí)，等式成立.

證明：當(dāng)γ=η時(shí), 根據(jù)引理1, 顯然有不等式(1)成立, 并且當(dāng)且僅當(dāng)圖G為正則圖時(shí)，等式成立. 因此, 圖G1和G2均為正則圖.

當(dāng)γ≠η時(shí), 不妨假設(shè)γ>η. 將圖G=G1▽G2(s,t) 的無符號(hào)拉普拉斯矩陣Q(G) 寫為分塊形式

其中：n=n1+n2,Q11是與G1的頂點(diǎn)相對(duì)應(yīng)的n1×n1矩陣,Q22是與G2的頂點(diǎn)相對(duì)應(yīng)的n2×n2矩陣. 設(shè)x是一個(gè)大于1 的實(shí)數(shù), 令矩陣

其中：In1是一個(gè)n1×n1單位矩陣,In2是一個(gè)n2×n2單位矩陣. 記U-1Q(G)U=B, 即

顯然, 矩陣Q(G)與B是相似矩陣, 它們的特征多項(xiàng)式的特征值均相同. 因而,q(G)=λ1(Q(G)) =λ1(B). 考慮矩陣B的n個(gè)行和r1,r2, …,rn, 可以得到：

當(dāng) 1 ≤l≤n1時(shí),

(2)

當(dāng)n1+1≤k≤n時(shí),

(3)

顯然,

令

解此等式可以得到

因?yàn)棣谩佴? 容易驗(yàn)證此時(shí)得到的x>1.故

q(G)≤

為使定理中的式(1)等號(hào)成立, 顯然證明過程中所有的不等式等號(hào)均要成立. 特別地,由式(2)和(3)可知： 當(dāng)1≤l≤n1時(shí), 有dl=γ; 當(dāng)n1+1≤k≤n時(shí), 有dk=η. 因此,G1和G2都是正則圖. 反之, 當(dāng)G1和G2都是正則圖時(shí), 等式也成立. 證畢.

設(shè)G= (V1,V2;E) 是一個(gè)二部圖, 如果對(duì)任意的u∈V1,v∈V2都有uv∈E, 則稱G為完全二部圖. 若|V1| =s, |V2| =t, 則記完全二部圖為Ks,t. 用W1,n-1表示一個(gè)孤立點(diǎn)與圈Cn-1中的每個(gè)頂點(diǎn)相鄰得到的輪圖.

推論1q(Ks,t) ≤s+t.

證明：對(duì)完全二部圖Ks,t, 在定理2中取值γ=s,η=t即可得. 證畢.

證明：對(duì)W1,n-1, 此時(shí)有s=1,t=n-1 并且γ= 3,η=n-1.代入定理2 即可得. 證畢.

參考文獻(xiàn)：

[3]ZHOU B X. On the signless Laplacian spectral radius of graphs with cut vertices[J]. Linear Algebra Appl, 2010, 433(5): 928-933.

[4]LI R, SHI J S. The minimum signless Laplacian spectral radius of graphs with given independence number[J]. Linear Algebra Appl, 2010, 433(8): 1614-1622.

[5]LIU H, LU M, TIAN F. On the Laplacian spectral radius of a graph[J]. Linear Algebra Appl, 2004, 376(1): 135-141.

[6]OLIVEIRA C S, de LIMA L S, de ABREU N M M,etal. Bounds on the index of the signless Laplacian of a graph[J]. Discrete Appl Math, 2010, 158(4): 355-360.

[7]YE M L, FAN Y Z, WANG H F. Maximizing signless Laplacian or adjacent spectral radius of graphs subject to fixed connectivity[J]. Linear Algebra Appl, 2010, 433(6): 1180-1186.

[8]BONDY J A, MURTY U S R. Graph theory with applications[M]. London: The Macmillan Press LTD, 1976: 32-51.

[9]MINC H. Nonnegative matrices[M]. New York: John Wiley & Sons Inc, 1988: 132-159.