有向圖的無符號拉普拉斯譜半徑的新上下界

何 軍， 劉衍民， 冉 杰

(遵義師范學院 數學學院， 貴州 遵義 563006)

1 預備知識

Q(G)=A(G)+D(G).

因為有向圖G是一個連通圖，則有向圖G的無符號拉普拉斯矩陣Q(G)為一個非負不可約的矩陣[1].設無符號拉普拉斯矩陣Q(G)的特征值由大到小排列為

q1(G)≥q2(G)≥…≥qn(G)，

則稱q1(G)為有向圖G的無符號拉普拉斯譜半徑.

對于無向圖G的無符號拉普拉斯譜半徑的研究已經取得了很多不錯的成果.最早，Cvetkovic等[1]給出了圖G的無符號拉普拉斯矩陣的定義,文獻[2-3]給出了圖G的無符號拉普拉斯譜半徑與拉普拉斯譜半徑之間的大小關系,但目前對有向圖G的無符號拉普拉斯譜半徑的研究工作還相對較少.

2016年，Xi等[4]利用有向圖頂點的度數，給出了有向圖G的無符號拉普拉斯譜半徑q1(G)的上界

(1)

2 主要結果

引理1[5]設M是一個非負不可約矩陣，則它的譜半徑ρ(M)是M的一個特征值，且存在一個正向量X，使得MX=ρ(M)X.

引理2[6]設M是一個n階非負方陣，Ri(M)是它的第i行的行和,則

min{Ri(M):vi∈E(G)}≤ρ(M)≤
max{Ri(M):vi∈E(G)}，

等式成立當且僅當行和相等.

定理1設G是一個n階連通有向圖,則

(2)

證明令有向圖G的出度對角矩陣

X=(x1,x2,…,xn)T

是矩陣D(G)-1Q(G)D(G)的最大特征值q1(G)所對應的特征向量.設

xi=max{xk:1≤k≤n}=1，
xj=max{xk:k≠i},

因為

D(G)-1Q(G)D(G)X=q1(G)X，

(3)

考慮(3)式中的第i個等式,有

又因為xi=1是特征向量里面的最大值，且

xj=max{xk:k≠i},

有

(4)

再考慮(3)式中的第j個等式,有

即

(5)

由(4)和(5)式可得

即

證畢.

定理2設G是一個n階連通有向圖,則

(6)

證明令有向圖G的出度對角矩陣

X=(x1,x2,…,xn)T

是矩陣D(G)-1Q(G)D(G)的最大特征值q1(G)所對應的特征向量.設

xi=min{xk:1≤k≤n}=1，
xj=min{xk:k≠i}，

因為

D(G)-1Q(G)D(G)X=q1(G)X，

(7)

考慮(7)式中的第i個等式,有

又因為xi=1是特征向量里面的最小值，且

xj=min{xk:k≠i},

有

(8)

再考慮(7)式中的第j個等式,有

即

(9)

由(8)和(9)式可得

即

證畢.

如果令定理1和定理2中的對角陣為

R=diag(1,1,…,1)，

那么可得定理3.

定理3設G是一個n階連通有向圖,則

3 數值例子

下面用數值例子來說明結果的有效性.設有向圖G的鄰接矩陣

那么有向圖G的無符號拉普拉斯矩陣譜半徑q1(G)=5.561 6.由(1)式可得q1(G)≤7.372 3，由(2)式可得q1(G)≤6.000 0,即定理1的結果優于文獻[4]中定理12的結果.

致謝遵義師范學院博士基金資助項目(遵師BS[2015]09)對本文給予了資助，謹表謝意.

[1] CVETKOVIC D, DOOB M, SACHS H. Spectra of Graphs[M]. New York:Academic Press,1980.

[2] SHU J L, HONG Y, WEN R K. A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph[J]. Linear Algebra Appl,2002,347(1/2/3):123-129.

[3] YAN C. Properties of spectra of graphs and line graphs[J]. Appl Math J Chin Uni,2002,17(3):371-376.

[4] XI W G, WANG L G. Sharp upper bounds on the signless Laplacian spectral radius of strongly connected digraphs[J]. Discussiones Mathematicae Graph Theory,2016,36(4):977-988.

[5] HORN A, JOHNSON C R. Matrix Analysis[M]. New York:Cambridge University Press,2013.

[6] BOZKURT S B, BOZKURT D. On the signless Laplacian spectral radius of digraphs[J]. Ars Combinatoria,2013,108(108):193-200.