有向圖的無(wú)符號(hào)拉普拉斯譜半徑的新上下界

何 軍， 劉衍民， 冉 杰

(遵義師范學(xué)院 數(shù)學(xué)學(xué)院， 貴州 遵義 563006)

1 預(yù)備知識(shí)

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

因?yàn)橛邢驁DG是一個(gè)連通圖，則有向圖G的無(wú)符號(hào)拉普拉斯矩陣Q(G)為一個(gè)非負(fù)不可約的矩陣[1].設(shè)無(wú)符號(hào)拉普拉斯矩陣Q(G)的特征值由大到小排列為

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

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

對(duì)于無(wú)向圖G的無(wú)符號(hào)拉普拉斯譜半徑的研究已經(jīng)取得了很多不錯(cuò)的成果.最早，Cvetkovic等[1]給出了圖G的無(wú)符號(hào)拉普拉斯矩陣的定義,文獻(xiàn)[2-3]給出了圖G的無(wú)符號(hào)拉普拉斯譜半徑與拉普拉斯譜半徑之間的大小關(guān)系,但目前對(duì)有向圖G的無(wú)符號(hào)拉普拉斯譜半徑的研究工作還相對(duì)較少.

2016年，Xi等[4]利用有向圖頂點(diǎn)的度數(shù)，給出了有向圖G的無(wú)符號(hào)拉普拉斯譜半徑q1(G)的上界

(1)

2 主要結(jié)果

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

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

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

等式成立當(dāng)且僅當(dāng)行和相等.

定理1設(shè)G是一個(gè)n階連通有向圖,則

(2)

證明令有向圖G的出度對(duì)角矩陣

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

是矩陣D(G)-1Q(G)D(G)的最大特征值q1(G)所對(duì)應(yīng)的特征向量.設(shè)

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

因?yàn)?/p>

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

(3)

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

又因?yàn)閤i=1是特征向量里面的最大值，且

xj=max{xk:k≠i},

有

(4)

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

即

(5)

由(4)和(5)式可得

即

證畢.

定理2設(shè)G是一個(gè)n階連通有向圖,則

(6)

證明令有向圖G的出度對(duì)角矩陣

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

是矩陣D(G)-1Q(G)D(G)的最大特征值q1(G)所對(duì)應(yīng)的特征向量.設(shè)

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

因?yàn)?/p>

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

(7)

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

又因?yàn)閤i=1是特征向量里面的最小值，且

xj=min{xk:k≠i},

有

(8)

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

即

(9)

由(8)和(9)式可得

即

證畢.

如果令定理1和定理2中的對(duì)角陣為

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

那么可得定理3.

定理3設(shè)G是一個(gè)n階連通有向圖,則

3 數(shù)值例子

下面用數(shù)值例子來(lái)說(shuō)明結(jié)果的有效性.設(shè)有向圖G的鄰接矩陣

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

致謝遵義師范學(xué)院博士基金資助項(xiàng)目(遵師BS[2015]09)對(duì)本文給予了資助，謹(jǐn)表謝意.

[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.