卡氏積圖的Laplacian 譜半徑的上界

周后卿(邵陽學(xué)院 理學(xué)院， 湖南 邵陽 422000)

卡氏積圖的Laplacian 譜半徑的上界

周后卿
(邵陽學(xué)院 理學(xué)院， 湖南 邵陽 422000)

對(duì)近年來圖的 Laplacian 譜半徑上界的研究成果進(jìn)行了簡單梳理. 利用2個(gè)圖的卡氏積圖的特征值,討論了2個(gè)循環(huán)圖的卡氏積圖的 Laplacian 譜半徑的上界問題,得到了幾個(gè)上界,推廣了已有文獻(xiàn)的結(jié)論.

卡氏積圖；Laplacian 矩陣；譜半徑；上界

圖譜理論是圖論重要的研究領(lǐng)域之一，在計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、信息科學(xué)、量子化學(xué)以及統(tǒng)計(jì)力學(xué)中均有廣泛應(yīng)用.利用代數(shù)的非負(fù)矩陣?yán)碚?借助組合數(shù)學(xué)的一些理論與技巧,研究圖譜與圖的結(jié)構(gòu)性質(zhì),與圖的有關(guān)不變量(譬如色數(shù)、度序列、直徑、圍長、連通度等)之間的關(guān)系.在圖譜理論中,為了研究圖的性質(zhì),常引入一些矩陣,如圖的鄰接矩陣、Laplacian 矩陣、距離矩陣等,這些矩陣與圖的結(jié)構(gòu)密切相關(guān). 通過矩陣論,特別是非負(fù)矩陣?yán)碚摗?duì)稱矩陣?yán)碚撘约敖M合矩陣論中的經(jīng)典結(jié)論,對(duì)圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行研究;通過圖的鄰接矩陣或 Laplacian 矩陣表示,建立圖的拓?fù)浣Y(jié)構(gòu)與圖的矩陣表示的置換相似不變量之間的聯(lián)系；同時(shí)，將圖論中的一些經(jīng)典結(jié)果用于非負(fù)矩陣?yán)碚摵徒M合矩陣論,從而推動(dòng)這些理論的發(fā)展.

圖的拉普拉斯矩陣及其特征值可用于多個(gè)領(lǐng)域的研究,并且在物理和化學(xué)理論中也有其物理解釋.早在19世紀(jì)中葉,KIRCHHOFF 就利用 Laplacian 矩陣譜研究了電流網(wǎng)絡(luò)，并給出了著名的矩陣-樹定理. 近幾十年來,學(xué)者們對(duì)圖的 Laplacian 譜半徑情有獨(dú)鐘,得到了許多深刻的結(jié)果.正如 MOHAR[1]所說，Laplacian 特征值比鄰接矩陣特征值更能反映圖的特質(zhì),而且比圖的鄰接譜更加自然和重要.對(duì)圖的鄰接矩陣和 Laplacian 矩陣特征值而言,最大特征值 (也即圖的譜半徑)是所有特征值中最重要的一個(gè)量.

隨著科學(xué)技術(shù)的進(jìn)步，新的研究方法不斷涌現(xiàn),借助計(jì)算機(jī)得到了許多更精確的結(jié)果.在網(wǎng)絡(luò)設(shè)計(jì)中,循環(huán)圖網(wǎng)絡(luò)結(jié)構(gòu)性能好,能長時(shí)間穩(wěn)定運(yùn)行;實(shí)用性強(qiáng),且具有可靠性、安全性、拓展性等特點(diǎn),因而,循環(huán)圖是一類重要的網(wǎng)絡(luò)拓?fù)鋱D.借助卡氏積圖,可以將網(wǎng)絡(luò)做大,并且能保持原有的一些特征,這種構(gòu)造網(wǎng)絡(luò)的方法行之有效.

在相關(guān)文獻(xiàn)的基礎(chǔ)上,本文著重研究循環(huán)圖的卡氏積圖的Laplacian半徑的上界.

1 圖的拉普拉斯譜半徑的上界

μ1(G)≥μ2(G)≥…≥μn-1(G)≥μn(G)=0.

關(guān)于圖的Laplacian譜半徑上界,學(xué)者們研究了一般圖,并且討論了樹、單圈圖、二部圖等特殊圖,得到了許多深刻的結(jié)果.

(1) ANDERSON等[2]利用相鄰2個(gè)頂點(diǎn)度給出了其上界：

μ(G)≤max{du+dv：uv∈E},

等式成立當(dāng)且僅當(dāng)G是一個(gè)正則二部圖或半正則二部圖.

(2) MERRIS[3]利用平均度改進(jìn)了上述上界，得到

μ(G)≤max{du+mu：u∈V},

(3) DAS[4]在文獻(xiàn)[2]的基礎(chǔ)上做了改進(jìn),證明了：

設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)的連通圖，則

μ(G)≤ max{du+dv-|NG(u)∩NG(v)|：

uv∈E(G)},

其中，NG(u)表示頂點(diǎn)u在G中的鄰點(diǎn)集,NG(u)∩NG(v)表示這2個(gè)鄰點(diǎn)集中的公共頂點(diǎn)數(shù).

(4) LI等[5]在上述文獻(xiàn)的基礎(chǔ)上,得到

等式成立當(dāng)且僅當(dāng)G是一個(gè)正則二部圖.

(5) SHI[6]利用最大、最小、平均度證明了：

設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)、直徑為D、最大度為Δ、最小度為δ、平均度為d的非正則連通圖.則

(6) STEVANOVIC[7]證明了具有頂點(diǎn)最大度的樹的Laplacian譜半徑的一個(gè)上界

(7) GUO[8]利用匹配數(shù)得到了下列結(jié)論：

(8) FENG等[9]討論了具有給定獨(dú)立數(shù)的單圈圖的Laplacian譜半徑問題,得到下列結(jié)果：

設(shè)G是一個(gè)具有n(n≥k+4)個(gè)頂點(diǎn)、k(k≥1)個(gè)懸掛點(diǎn)的單圈圖，則μ(G)≤μ(U4,k)等式成立當(dāng)且僅當(dāng)G?U4,k，這里，Ug,k表示頂點(diǎn)為n(n≥k+4)的單圈圖，由圈圖Cg的一個(gè)頂點(diǎn)吸附k條長度幾乎相等的路(這些路長度最多相差1)而得到.

文獻(xiàn)[9]還得到了下列結(jié)論：

(9) GRONE 等[10]獲得了以下二部圖結(jié)果：

設(shè)G是一個(gè)連通圖,則μ(G)≤q(G)等式成立當(dāng)且僅當(dāng)G是一個(gè)二部圖,這里q(G)表示矩陣Q(G)=D(G)+A(G)的最大特征值.

設(shè)Βn,m表示所有頂點(diǎn)為n,邊為m的二部圖，Gm表示在Βn,m中具有最大 Laplacian譜半徑的一個(gè)二部圖.

(10) LI等[11]證明了以下結(jié)果：

m≠t(n-t),則μ(Gm)<μ(Gm+1);

(11) PATRA 等[12]得到了以下結(jié)論：

設(shè)G是一個(gè)二部圖,G′是由G中的一個(gè)頂點(diǎn)鄰接另外一個(gè)新頂點(diǎn)所得，則μ(G)≤μ(G′).更一般地(見文獻(xiàn)[1]),在圖G中插入一條新邊e，得到另一個(gè)圖G′,即G′=G+e.則有μ(G)≤μ(G′).

(12) MOHAR[1]證明了下列定理：

設(shè)G=G1∪G2是圖G的因子分解,則

max(μ(G1),μ(G2))≤μ(G)≤μ(G1)+μ(G2).

(13) 周后卿[13]研究了圖在二元運(yùn)算下,Cartesian 積圖的最大Laplacian特征值的上界問題.

(14) 對(duì)于具有n個(gè)頂點(diǎn)的Halin圖G,JIA等[14]證明了其Laplacian譜半徑滿足不等式：

n-1<μ(G)≤n,

右邊不等式成立當(dāng)且僅當(dāng)G=Wn，Wn表示有n個(gè)頂點(diǎn)的輪圖.

(15) LIU等[15]討論了具有最大Laplacian譜半徑的極圖問題.

(16) XING等[16]得到了具有固定控制數(shù)的Laplacian譜半徑，并刻畫了其極圖.

2 引理、結(jié)論及其證明

循環(huán)圖具有n個(gè)頂點(diǎn)的循環(huán)圖G(n,S)可以定義為循環(huán)群上的一個(gè)Cayley圖,其頂點(diǎn)是循環(huán)群Zn上的元素,頂點(diǎn)i,j相連當(dāng)且僅當(dāng)j-i是S中的元素,這里S是Zn{0}的一個(gè)子集.循環(huán)圖的矩陣是一個(gè)循環(huán)矩陣,循環(huán)圖是一個(gè)正則圖,每個(gè)頂點(diǎn)的度相等.

卡氏積圖設(shè)G=(V(G),E(G)),H=(V(H),E(H))是2個(gè)簡單的連通圖,那么G與H的卡氏積圖G×H是這樣的圖： 其頂點(diǎn)集為V(G×H)=V(H)×E(H);G×H中任何2個(gè)頂點(diǎn)(u,v)與(s,t)相鄰當(dāng)且僅當(dāng)u=s且v與t在H中相鄰；或v=t且u與s在G中相鄰，這里u,s∈V(G),v,t∈V(H).

為了證明本文結(jié)論，需要下列引理：

引理1[17]設(shè)圖G與H的頂點(diǎn)分別為n,m,圖G與H的Laplacian特征值分別為

μ1(G)≥μ2(G)≥…≥μn-1(G)≥μn(G)=0,

μ1(H)≥μ2(H)≥…≥μn-1(H)≥μn(H)=0，

則G與H的笛卡爾乘積G×H的Laplacian矩陣的特征值為

μi(G)+μj(H)， 1≤i≤n,1≤j≤m.

引理2[18]設(shè)G是一個(gè)頂點(diǎn)為n(n≥4)的連通、 非完全圖.則G的鄰接矩陣的最小特征值λmin(G)滿足

λmin(G)≥

對(duì)于一個(gè)γ-正則圖G,其Laplacian特征值與其鄰接矩陣特征值之間的關(guān)系為

μj=γ-λj, 1≤j≤n,

其中,λj為G的鄰接矩陣的特征值.

定理1設(shè)G與H是2個(gè)頂點(diǎn)分別為n,m(n,m≥4), 度分別為s,t的循環(huán)圖.則G與H的卡氏積圖G×H的Laplacian譜半徑滿足不等式：

其中,Ν,E,O分別表示正整數(shù)集、偶數(shù)集、奇數(shù)集.并且,

證明不妨設(shè)Ν,Ε,Ο分別表示正整數(shù)集、偶數(shù)集、奇數(shù)集.

(1) 由引理2可知,

所以,

由引理1,結(jié)論得證.

(2) 由引理3,當(dāng)n∈Ε時(shí),

即

所以有

同理,當(dāng)m∈Ε時(shí)可得

記

由引理1得

μ(G×H)≤s+t+p1+q1.

(3) 當(dāng)n∈O時(shí)，

λmin(G)≥

即

-λmin(G)≤

所以有

同理,當(dāng)m∈Ο時(shí)可得

記

于是,由引理1得

μ(G×H)≤s+t+p2+q2.

(4) 當(dāng)n∈E,m∈O時(shí)，

即

μ(G)≤s+p1,μ(H)≤t+q2.

根據(jù)引理1,有

μ(G×H)≤s+t+p1+q2.

(5) 當(dāng)n∈Ο,m∈Ε時(shí),

即

μ(G)≤s+p2,μ(H)≤t+q1.

由引理1，有

μ(G×H)≤s+t+p2+q1.

定理得證.

定理2設(shè)G與H是2個(gè)頂點(diǎn)分別為n,m, 度分別為s,t的循環(huán)圖.則G與H的卡氏積圖G×H的Laplacian譜半徑

μ(G×H)≤2(s+t)-k-l,

等式成立當(dāng)且僅當(dāng)G,H是完全圖,其中，

k=|NG(u)∩NG(v)|,uv∈E(G),

l=|NH(u′)∩NH(v′)|,u′v′∈E(H).

證明由

μ(G)≤max{du+dv-|NG(u)∩NG(v)|：uv∈E(G)}

可知,對(duì)于循環(huán)圖G,有

μ(G)≤2du-|NG(u)∩NG(v)|=

2s-|NG(u)∩NG(v)|=2s-k,

這里,|NG(u)∩NG(v)|=k,uv∈E(G).

同理,對(duì)于循環(huán)圖H,有μ(H)≤2t-l,其中,

l=|NH(u′)∩NH(v′)|,u′v′∈E(H).

由引理1,便可推得上述結(jié)論.

特別地,當(dāng)G,H是完全圖時(shí)，

s=n-1,t=m-1,k=n-2,l=m-2.

因而,有

μ(G×H)=n+m.

例1循環(huán)圖G=G(15,S1),H=H(20,S2)，

S1={3,5,6,9,10,12},S2={4,5,8,10,12,15,16},分別是度為6,7的正則圖.由定理1可得μ(G×H)≤30.5 以及μ(G×H)≤40.2；由定理2得到μ(G×H)≤20.借助計(jì)算軟件,實(shí)際求得

μ(G)=8,μ(H)=9,μ(G×H)=17.

說明定理2的結(jié)果準(zhǔn)確性更高.

衷心感謝審稿專家給予本文的寶貴意見！

[1] MOHAR B.TheLaplacianSpectrumofGraphs-Graphtheory,CombinatoricsandApplications[M]. New York： John Wiley, 1991.

[2] ANDERSON W N, MORLEY T D. Eigenvalues of the Laplacian of a graph[J].LinearandMultilinearAlgebra,1985, 18： 141-145.

[3] MERRIS R. A note on Laplacian graph eigenvalues[J].LinearAlgebraanditsApplications,1998,285： 33-35.

[4] DAS K. An improved upper bound for Laplacian graph eigenvalues[J].LinearAlgebraanditsApplications. 2003,368 ： 269-278.

[5] LI J S, ZHANG X D. On the Laplacian eigenvalues of a graph [J].LinearAlgebraanditsApplications, 1998,285： 305-307.

[6] SHI L S. The spectral radius of irregular graphs[J].LinearAlgebraanditsApplications, 2009,431： 189-196.

[7] STEVANOVIC D. Bounding the largest eigenvalue of trees in terms of the largest vertex degree[J].LinearAlgebraanditsApplications,2003, 360： 35-42.

[8] GUO J M . On the Laplacian spectral radius of a tree[J].LinearAlgebraanditsApplications,2003, 368： 379-385

[9] FENG L H，YU G H, ILIC A.The Laplacian spectral radius for unicyclic graphs with given independence number[J].LinearAlgebraanditsApplications,2010, 433： 934-944.

[10] GRONE R, MERRIS R, SUNDER V S. The Laplacian spectrum of a graph[J].SIAMJournalonMatrixAnalysisandApplications,1990,11： 218-238.

[11] LI J X, SHIU W C,CHAN W H. On the Laplacian spectral radii of bipartite graphs[J].LinearAlgebraanditsApplications, 2011, 435 ： 2183-2192.

[12] PATRA K L, SAHOO B K, BHUBANESWAR. Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth[J].CzechoslovakMathematicalJournal, 2013,63 (138)： 909-922.

[13] 周后卿.Cartesian積圖的最大拉普拉斯特征值[J].邵陽學(xué)院學(xué)報(bào),2011(1)： 5-7.

ZHOU H Q . The largest eigenvalue of Laplacian matrix of cartesian product graph[J].JournalofShaoyangUniversity, 2011(1)： 5-7.

[14] JIA H C, XUE J. On the Laplacian spectral radii of Halin graphs[J].JournalofInequalitiesandApplications, 2017： 73.

[15] LIU M H, DAS K C,LAI H J.The (signless) Laplacian spectral radii ofc-cyclic graphs withnvertices, girthgandkpendant vertices[J].LinearandMultilinearAlgebra, 2017,65(5)： 869-881.

[16] XING R D,ZHOU B. Laplacian and signless Laplacian spectral radii of graphs with fixed domination number[J].MathematischeNachrichten,2015,288(4)： 476-480.

[17] CVETKOVIC D, DOOB M, SACHS H.SpectraofGraphs,TheoryandApplications[M]. Heidelberg： Johann Ambrosius Barth, 1995.

[18] BELL F K, CVETKOVIC D, ROWLINSON P. Graphs for which the least eigenvalue is minimal[J].LinearAlgebraanditsApplications, 2008, 429： 234-241.

[19] YU G D, FAN Y Z, WANG Y. The least eigenvalue of graphs[J].JournalofMathematicalResearchwithApplications, 2012, 32(6)： 659-665.

ZHOU Houqing
(CollegeofScience,ShaoyangUniversity,Shaoyang422000,HunanProvince,China)

We organize the results of the upper bounds of Laplacian spectral radius for some graphs in the last few years and explore the upper bounds of Laplacian spectral radius for the Cartesian product of circulant graphs based on the eigenvalues of the Cartesian product of two graphs. Our results generalize and improve the conclusion of the existing literatures.

Cartesian product graphs; Laplacian matrix; spectral radius; upper bound

2016-07-25.

國家自然科學(xué)基金資助項(xiàng)目(61672356)；湖南省教育廳科學(xué)研究項(xiàng)目(2015C1235,2016C1434).

周后卿(1963—)，ORCID： http： //orcid.org/000-0002-9813-1687,男，碩士，教授，主要從事圖論及其應(yīng)用研究， E-mail： zhouhq2004@163.com.

10.3785/j.issn.1008-9497.2018.01.002

O 157.5

A

1008-9497(2018)01-010-04

UpperboundsofLaplacianspectralradiusfortheCartesianproductgraphs.Journal of Zhejiang University (Science Edition)，2018, 45(1)： 010-013