周琨強(qiáng)，王維忠

(蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州 730070)

0 引 言

文中所涉及的圖都是簡單圖. 設(shè)圖G的頂點(diǎn)集V(G)={v1,v2,…,vn}, 邊集E(G)={e1,e2,…,em}. 設(shè)A(G)和D(G)=diag(d1,d2,…,dn)(di是圖G中頂點(diǎn)vi的度)分別為圖G的鄰接矩陣與度對(duì)角矩陣, 則圖G的拉普拉斯矩陣定義為L(G)=D(G)-A(G)[1-2]. 由于L(G)是半正定的實(shí)對(duì)稱矩陣, 從而其特征值滿足u1≥u2≥…≥un=0. 2008年, 柳柏濂等[3]引入了圖G的擬拉普拉斯能量(LEL)的概念, 即L(G)的所有特征值的算術(shù)平方根之和, 亦即

在理論化學(xué)中,LEL是一個(gè)與圖的拉普拉斯譜密切相關(guān)的分子描述子, 是一個(gè)新的拓?fù)渲笜?biāo). 相比較化學(xué)研究中使用的其它拓?fù)渲笜?biāo)，LEL不僅能夠很好地描述大部分描述子已經(jīng)證明了的性質(zhì), 而且也能夠描述一些更難獲得的性質(zhì), 如沸點(diǎn)、熔點(diǎn)、分配函數(shù)等.關(guān)于LEL的最新研究成果參見文獻(xiàn)[4-11]等.

H-聯(lián)圖(∨H(G1,G2,…,Gk))是在不交圖G1,G2,…,Gk基礎(chǔ)上, 對(duì)于H中的任意頂點(diǎn)i,j, 若ij∈H, 則將Gi的所有頂點(diǎn)與Gj的每一個(gè)頂點(diǎn)相連所得到的圖如圖1 所示，其中圖H的頂點(diǎn)集為{1,2,…,k}. 特別地, 如果H=P2, 那么，∨P2(G1,G2)就是常見的普通聯(lián)圖G1∨G2[12-13]. 目前,H-聯(lián)圖的研究已取得了一些成果, 如文獻(xiàn)[12]較早地給出了它的鄰接特征多項(xiàng)式, 文獻(xiàn)[13-14]確定了它的鄰接譜和拉普拉斯譜, 文獻(xiàn)[15]刻畫了這類圖的無符號(hào)拉普拉斯譜和正規(guī)拉普拉斯譜. 在文獻(xiàn)[13-14]的基礎(chǔ)上, 本文對(duì)H在一定限制條件下, 給出了H-聯(lián)圖的擬拉普拉斯能量的上界.

圖1 {K1,K2,K2}的H-聯(lián)圖Fig.1 The H-join graph of disjoint graphs K1,K2,K2

1 H-聯(lián)圖的擬拉普拉斯能量

為了敘述方便, 引入兩個(gè)記號(hào):a+SpecL(Gi)(aSpecL(Gi))表示給SpecL(Gi)中的每個(gè)元素都加上常數(shù)a(乘以常數(shù)a).

SpecL(∨H(G1,G2,…,Gk))=

證明設(shè)L(Gi)的特征值為ui1≥ui2≥…≥uini=0(i=1,2,…,k), 則由引理1可知,

又由引理1可得

(((N-n1)-n2)(n2-1),((N-n1)-n3)(n3-1),…,((N-n1)-nk)(nk-1))∪

(0,(N-n1)(k-2)),

則

((N-n2)(n2-1),(N-n3)(n3-1),…,(N-nk)(nk-1))∪(0,N(k-1)),

(1)

同理可得

((N-n1)(n1-1),(N-n3)(n3-1),…,(N-nk)(nk-1))∪(0,N(k-1)),

(2)

……

((N-n1)(n1-1),(N-n2)(n2-1),…,(N-ni-1)(ni-1-1))∪

(N-ni+1)(ni+1-1,…,(N-nk)nk-1)∪(0,N(k-1)),

(3)

……

((N-n1)(n1-1),(N-n2)(n2-1),…,(N-nk-1)(nk-1-1))∪(0,N(k-1)).

(4)

又由引理1可知

SpecL(∨H(G1,G2,…,Gk))=(N-n1+(u11,u12,…,u1(n1-1)))∪

(N-n2+(u21,u22,…,u2(n2-1)))∪…∪

(N-nk+(uk1,uk2,…,uk(nk-1)))∪(0,N(k-1)),

(5)

以及

(0,N(k-1)).

(6)

由式(1)可得

(7)

由式(2)可得

(8)

由式(3)可得

(9)

由式(4)可得

(10)

由式(5)可得

(11)

由式(6)可得

(12)

將式(7)～式(10)等k個(gè)等式左右兩端分別求和, 則有

(13)

結(jié)合式(12)和(13)兩式可得

(14)

再結(jié)合式(11)和(14)兩式可得

定理得證.

(15)

證明設(shè)L(Gi)的特征值為ui1≥ui2≥…≥uini=0(i=1,2,…,k), 則由引理1可知,

SpecL(∨H(G1,G2,…,Gk))=(N-n1+(u11,u12,…,u1(n1-1)))∪

(N-n2+(u21,u22,…,u2(n2-1)))∪…∪(N-nk+(uk1,uk2,…,uk(nk-1)))∪(0,Nk-1).

(16)

由式(16)可知

(17)

注2定理2利用H和Gi的階數(shù)以及Gi的擬拉普拉斯能量的值(i=1,2,…,k), 刻畫了相應(yīng)H-聯(lián)圖的擬拉普拉斯能量的上界.

證明由定理2可知

(18)

引理2[14]設(shè)H的度序列為d1,d2,…,dk,Gi(i=1,2,…,k)均為n階圖, 則

SpecL(∨H(G1,G2,…,Gk))=

定理3設(shè)H的度序列為d1,d2,…,dk,Gi(i=1,2,…,k)均為n階圖, 則

證明設(shè)L(Gi)的特征值為ui1≥ui2≥…≥uini=0(i=1,2,…,k), 則由引理2可知,

SpecL(∨H(G1,G2,…,Gk))=(nd1+(u11,u12,…,u1(n-1))∪(nd2+(u21,u22,…,u2(n-1))∪…∪

(ndk+(uk1,uk2,…,uk(n-1))∪(nSpecL(H)).

(19)

由式(19)可知

(20)

SpecL(∨H(G1,G2,…,Gs+t))=

{0,NX+NY,NXs-1,NYt-1}.

LEL(∨H(G1,G2,…,Gs+t))≤

證明設(shè)L(Gi)的特征值為ui1≥ui2≥…≥uini=0(i=1,2,…,s+t), 則由引理3可知

SpecL(∨H(G1,G2,…,Gs+t))=(NX+(u11,u12,…,u1(n1-1)))∪(NX+(u21,u22,…,u2(n2-1)))∪…∪

(NX+(us1,us2,…,us(ns-1)))∪(NY+(u(s+1)1,u(s+1)2,…,u(s+1)(ns+1-1))∪…∪

(NY+(u(s+t)1,u(s+t)2,…,u(s+t)(ns+t-1))),

(21)