婁源源， 吳寶豐

(上海理工大學(xué)理學(xué)院，上海 200093)

關(guān)于H-聯(lián)圖的拉普拉斯特征值

婁源源， 吳寶豐

(上海理工大學(xué)理學(xué)院，上海 200093)

H-聯(lián)圖是在不交圖G1，G2，…，Gk的基礎(chǔ)上，對(duì)于H中的任意兩點(diǎn)i，j，若ij∈E(H)，則將Gi的每一點(diǎn)與Gj的每一點(diǎn)相連所得到的圖，其中，H的頂點(diǎn)集為{1，2，…，k}.特別地，{G1，G2}的P2-聯(lián)圖就是普通聯(lián)圖G1∨G2.本文研究了H-聯(lián)圖的拉普拉斯特征多項(xiàng)式，給出了H-聯(lián)圖的拉普拉斯譜與圖G1，G2，…，Gk以及基圖H的拉普拉斯譜之間的關(guān)系.進(jìn)一步研究了基圖分別為完全圖、完全二部圖時(shí)的H-聯(lián)圖，給出了Kk-聯(lián)圖和Ks，t-聯(lián)圖的拉普拉斯譜以及相應(yīng)的特征多項(xiàng)式.另外，證明了當(dāng)基圖H是完全圖、完全二部圖或階數(shù)小于等于4的圖(除P4外)時(shí)，L-整圖{G1，G2，…，Gk}的H-聯(lián)圖也是L-整的.

H-聯(lián)圖；拉普拉斯特征值；整圖

1 基本概念

圖G的鄰接矩陣定義為A(G)=(aij)，其中當(dāng)ij∈E(G)時(shí)，aij=1；否則，aij=0.圖G的拉普拉斯矩陣定義為L(zhǎng)(G)=D(G)-A(G)，其中D(G)=diag(d1，d2，…，dn)為G的度對(duì)角矩陣.

考慮方陣M，M的特征多項(xiàng)式表示為P(M，x)= det(x I-M)，M的特征值即為P(M，x)的根，其中，0特征值的重?cái)?shù)稱為M的零度.M的譜Spec(M)是由M的特征值組成的多重集合，用符號(hào)a+ Spec(M)(或aSpec(M))表示Spec(M)中的每一個(gè)元素加上a(或乘以a).特別地，圖G的拉普拉斯特征多項(xiàng)式記為，圖G的拉普拉斯譜記為SpecL(G)(即L(G)的譜).若L(G)的特征值全為整數(shù)，則稱圖G是L-整的.

定義1[1-2]設(shè)圖H的頂點(diǎn)集為{1，2，…，k}，Gi為ni階圖(i=1，2，…，k)，則{G1，G2，…，Gk}的H-聯(lián)圖，記作∨H{G1，G2，…，Gk}，它是在G1，G2，…，Gk的基礎(chǔ)上，對(duì)于H中的任意兩點(diǎn)i，j，若ij∈E(H)，則將Gi的每一點(diǎn)與Gj的每一點(diǎn)相連所得到的圖.圖H稱為聯(lián)圖∨H{G1，G2，…，Gk}的基圖.

特別地，當(dāng)基圖H=P2時(shí)，P2-聯(lián)圖就是普通的聯(lián)圖，即∨P2{G1，G2}=G1∨G2.當(dāng)所有Gi(i= 1，2，…，k)相同，均為G時(shí)，為方便起見，用符號(hào)H⊙G來代替∨H{G，G，…，G}，即H的每一點(diǎn)都被“吹大”成G后所得到的圖.

聯(lián)圖的特征多項(xiàng)式(或譜)已被廣泛研究，如文獻(xiàn)[1]較早地研究了它的鄰接特征多項(xiàng)式，文獻(xiàn)[2]研究了它的鄰接譜和拉普拉斯譜.另外，P2-聯(lián)圖在圖的標(biāo)號(hào)理論研究中也引起了高度關(guān)注.

2 H-聯(lián)圖的拉普拉斯特征多項(xiàng)式

定義2 設(shè)圖H的頂點(diǎn)集為{1，2，…，k}，Gi為ni階圖(i=1，2，…，k)，考慮H-聯(lián)圖∨H{G1，G2，…，Gk}，定義:

由定義可知，Lπ的行和均為0，從而0是它的一個(gè)特征值，Lπ是奇異矩陣.不難驗(yàn)證，對(duì)于H-聯(lián)圖G=∨H{G1，G2，…，Gk}，它在劃分π:V(G)= V(G1)∪·…∪·V(Gk)下的L-因子矩陣就是L(G)基于該劃分的商矩陣.

引理2 設(shè)圖H的頂點(diǎn)集為{1，2，…，k}，Gi為ni階圖(i=1，2，…，k)，若G=∨H{G1，G2，…，Gk}，Lπ為G的關(guān)于劃分π:V(G)=V(G1)∪·…∪·V(Gk)的L-因子矩陣，CL(H)同定義2，則矩陣Lπ與CL(H)相似.

3 L-整圖

整圖的譜完全由整數(shù)構(gòu)成，哪些圖是整圖呢?該問題由Harary等[6]于1973年針對(duì)鄰接譜提出，同時(shí)指出了此類問題具有一定的難度.整圖的數(shù)量是無限的，而且在各類圖集中都可能存在，但是，它們?nèi)匀皇欠浅Ｏ∩俚?，并且難以找到.例如，最大度固定的整圖，其數(shù)量是相當(dāng)有限的.通常是利用已知的整圖通過圖的運(yùn)算來構(gòu)造新的整圖[6-8].對(duì)于拉普拉斯譜，完全圖、完全二部圖都是L-整的，所以，

引理4 設(shè)H為k階樹，則H是L-整圖，當(dāng)且僅當(dāng)H為星圖K1，k-1.

證明 星圖是L-整的，所以，充分性顯然，現(xiàn)證必要性.

當(dāng)k=1，2或3時(shí)，此時(shí)的樹都是唯一的，即星圖，結(jié)論成立.

當(dāng)k≥4時(shí)，若H≠K1，k-1，則H的直徑d≥3，由引理3可知

再根據(jù)H的連通性可知，0＜a(H)＜0.59，從而a(H)不是整數(shù)，即L(H)的第二小特征值不是整數(shù).這與H是L-整圖矛盾，所以，H=K1，k-1.

定理7 設(shè)H為k階樹，G為L(zhǎng)-整圖，則H⊙G是L-整的，當(dāng)且僅當(dāng)H=K1，k-1.

證明 由推論6和引理4可知結(jié)論成立.

[1] Schwenk A J.Computing the characteristic polynomialof a graph[J].Lecture Notes in Mathematics，1974，406:153-172.

[2] Cardoso D M，de Freitas M A A，Martins E A，et al. Spectra of graphs obtained by a generalization of the join graph operation[J].Discrete Mathematics，2013，313(5):733-741.

[3] Wang J F，Belardob F.A note on the signless Laplacian eigenvalues of graphs[J].Linear Algebra and Its Applications，2011，435(10):2585-2590.

[4] Cvetkovic′D，Rowlinson P，Simic′S.An introduction to the theory of graph spectra[M].New York:Cambridge University Press，2010.

[5] Cardoso D M，Delorme C，Rama P.Laplacian eigenvectors and eigenvalues and almost equitable partitions [J].European Journal of Combinatorics，2007，28(3):

[6] Harary F，Schwenk A J.Which graphs have integral spectra?[J].Lecture Notes in Mathematics，1974，406:45-51.

[7] Grone R，Merris R.The Laplacian spectrum of a graph II[J].SIAM Journal on Discrete Mathernatics，1994，7 (2):221-229.

[8] 陳永玲，何常香.二部雙圈圖的拉普拉斯系數(shù)[J].上海理工大學(xué)學(xué)報(bào)，2012，34(5):481-486.

[9] Grone R，Merris R，Sunder V S.The Laplacian spectrum of a graph[J].SIAM Journal on Matrix Analysis and Applications，1990，11(2):218-238.

[10] 沈富強(qiáng)，吳寶豐.最小Q-特征值為給定整數(shù)的一類圖[J].上海理工大學(xué)學(xué)報(bào)，2014，36(5):425-428.

(編輯:石 瑛)

Laplacian Eigenvalues on the H-Join Graphs

LOU Yuanyuan， WUBaofeng
(College of Science，University of Shanghai for Science and Technology，Shanghai 200093，China)

The H-join graph is obtained on the basis of disjoint graphs G1，G2，…，Gkand by joining each vertex of Gito each vertex of Gjwhenever i is adjacent to j in H.In particular，the P2-join graphs{G1，G2}is the ordinary join graph G1∨G2.The Laplacian characteristic polynomial of the H-join graph was studied，and the relations between the Laplacian spectrum of the H-join graph and those of the graphs Gi(i=1，2，…，k)and H were obtained，especially for the Kk-join graph and Ks，t-join graph.Moreover，the fact was proven that the H-join of Laplacian integral graphs{G1，G2，…，Gk}is also Laplacian integral when H is the complete graph，the complete bipartite graph or the graph of order not greater than 4 except for P4.

H-join graph；Laplacian eigenvalue；integral graph

O 157.5

A

2013-12-18

國(guó)家自然科學(xué)基金資助項(xiàng)目(11301340，11201303)；上海市自然科學(xué)基金資助項(xiàng)目(12ZR1420300)第一作者:婁源源(1988-)，男，碩士研究生.研究方向:代數(shù)圖論.E-mail:xylouyuanyuan@163.com

吳寶豐(1978-)，男，講師.研究方向:代數(shù)圖論.E-mail:baufern@usst.edu.cn