一些拉普拉斯譜確定的圖

王玉潔,　何常香

(上海理工大學(xué) 理學(xué)院,上?！?00093)

?

一些拉普拉斯譜確定的圖

王玉潔,何常香

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

摘要：如果與圖G同拉普拉斯譜的圖都與圖G同構(gòu),則稱圖G由它的拉普拉斯譜確定.給出了三類基圖為B(P3,P3,P3)(即連接2點(diǎn)的3條長(zhǎng)為2的內(nèi)不交的路)的連通二部雙圈圖類H(n;n1),H(n;n1,n2)和B(n;n1,n2).證明了H(n;n1),H(n;n1,n2)和B(n;n1,n2)是拉普拉斯譜確定的,且與完全圖經(jīng)并接運(yùn)算后所得圖也是拉普拉斯譜確定的.

關(guān)鍵詞：二部雙圈圖; 拉普拉斯矩陣; 拉普拉斯譜確定

1問題的提出

所考慮的圖都是簡(jiǎn)單連通無向圖.n階連通圖G=(V,E)稱為雙圈圖,若G中恰含n+1條邊.用A(G)=(aij)表示圖G的鄰接矩陣,其中,若vivj∈E(G),則aij=1;若vivj?E(G),則aij=0.用D(G)=diag(d1,d2,…,dn)表示圖G的頂點(diǎn)度對(duì)角矩陣.矩陣L(G)=D(G)-A(G)為圖G的拉普拉斯矩陣,L(G)的特征多項(xiàng)式定義為G的拉普拉斯特征多項(xiàng)式,記為

令μ1≥μ2≥…≥μn=0是L(G)的所有特征值,這些特征值構(gòu)成的多重集合稱為圖G的拉普拉斯譜.如果與圖G同拉普拉斯譜的圖都與圖G同構(gòu),則稱圖G由它的拉普拉斯譜確定,簡(jiǎn)記為DLS.

“哪些圖可由它們的譜確定？”這一問題是在1957年發(fā)現(xiàn)第一對(duì)同譜圖后提出的[1].關(guān)于同譜圖的研究是圖譜理論中一個(gè)有趣且困難的問題.1966年,Fisher在考慮Kac[2]提出的“一個(gè)人能否聽到鼓聲的形狀”的問題時(shí),研究的正是圖的譜確定問題.文獻(xiàn)[3]提到恰有n個(gè)點(diǎn)的圖,不能由譜確定的圖比能由譜確定的圖多.在這個(gè)結(jié)果出現(xiàn)以后,研究圖的譜確定性問題變得熱門起來.之后,人們又開始研究拉普拉斯譜確定的問題.如文獻(xiàn)[4]證明了T-型樹是拉普拉斯譜確定的,文獻(xiàn)[5]證明了雙星圖由其拉普拉斯譜確定,文獻(xiàn)[6-7]分別證明了型圖和3-玫瑰圖是拉普拉斯譜確定的.文獻(xiàn)[8-10]分別證明了棒棒糖圖、太陽圖和沙漏圖是拉普拉斯譜確定的.文獻(xiàn)[11]研究了雙圈圖的無符號(hào)拉普拉斯特征多項(xiàng)式系數(shù).文獻(xiàn)[12]研究了關(guān)于H-聯(lián)圖的拉普拉斯特征值.受這些工作的啟發(fā),本文研究了二部雙圈圖與完全圖并接后所得圖的拉普拉斯譜確定性.

2基本定義

不含懸掛點(diǎn)的雙圈圖可以分為B(p,l,q)(其中,l≥0,p≥3,q≥3)和B(Ps,Pm,Pl)(其中,2≤m≤min{s,l})兩種.

B(p,l,q)是在圈Cp中的點(diǎn)u和圈Cq中的點(diǎn)v加1條長(zhǎng)為l的新路uv1v2…vl-1v得到的圖,如圖1所示.特別地,當(dāng)l=0時(shí),B(p,0,q)是由唯一公共點(diǎn)u(或v)的圈CP(或Cq)組成的圖.

B(Ps,Pm,Pl)是由點(diǎn)x到點(diǎn)y的3條內(nèi)點(diǎn)不交的路組成的圖.設(shè)這3條路分別為:長(zhǎng)為s-1的路xv1v2…vs-2y,長(zhǎng)為m-1的路xu1u2…um-2y和長(zhǎng)為l-1的路xw1w2…wl-2y,如圖1所示.

可將雙圈圖按其基圖分為如下兩類:

圖1　雙圈圖B(p,l,q)和雙圈圖B(Ps,Pm,Pl)

3基本引理

現(xiàn)介紹一些證明主要結(jié)論時(shí)需要用到的引理.本文圖G的拉普拉斯特征多項(xiàng)式記為

引理1[13]對(duì)于圖G,由其拉普拉斯譜可以確定圖G的以下參數(shù):

a. 頂點(diǎn)數(shù);

b. 邊數(shù);

c. 連通分支數(shù);

d. 頂點(diǎn)度的平方和;

e. 生成樹個(gè)數(shù).

引理2[13]設(shè)圖G的頂點(diǎn)集和邊集分別為V(G)≠φ和E(G)≠φ,有

引理3[14]圖G的拉普拉斯特征多項(xiàng)式中xk的系數(shù)的絕對(duì)值

式中:Fk是圖G的恰有k個(gè)連通分支的生成森林構(gòu)成的集合;γ(F)為生成森林F∈Fk的各連通分支頂點(diǎn)數(shù)的乘積.

引理4[15]設(shè)圖G是一個(gè)恰有n個(gè)頂點(diǎn)和m條邊的圖,(d1,d2,…,dn)為圖G的度序列,則在G的拉普拉斯特征多項(xiàng)式中,

式中:τ(G)為圖G的生成樹數(shù)目;nG(C3)為圖G中三角形數(shù)目.

引理5設(shè)(d1,d2,…,dn)和(d′1,d′2,…,d′n)分別為圖G和G′的度序列,記

若G與圖G′有相同的拉普拉斯譜,則q3(G)=q3(G′).

證明若G與G′拉普拉斯同譜,則l3(G)=l3(G′).由引理1及引理4可知

進(jìn)一步有

（2）當(dāng)攪拌機(jī)將物料倒放到運(yùn)料卡車上時(shí)，卡車需要前后移動(dòng)，按前后中的順序分為三堆，以減少粗集料發(fā)生離析的現(xiàn)象。

由生成樹的定義,可得引理6.

引理6設(shè)圖G是雙圈圖,τ(G)是G的生成樹數(shù)目.

圖2　雙圈圖B(P3,P3,P3)和雙圈圖B(3,l,4)

證明若圖G和G′同拉普拉斯譜,則G′也連通,且G′的邊數(shù)與G的邊數(shù)相同,故G′也是雙圈圖.由引理6可知,τ(G)=12,故τ(G′)=12.

若τ(G′)=12,分兩種情況討論.

引理8[16]設(shè)圖G是恰有n個(gè)點(diǎn)、m條邊的連通DLS圖,如果圖G同時(shí)滿足以下3個(gè)條件:

b. 圖G的邊連通度為1;

c.n-m+1≤n-5,即m≥6.

則圖G與完全圖Kr(其中r為任意整數(shù))并接后所得圖G∨Kr也為DLS圖.

4圖H(n;n1)∨Kr是DLS圖

研究二部雙圈圖H(n;n1)(圖3)與完全圖Kr并接后所得圖H(n;n1)∨Kr(其中r為任意非負(fù)整數(shù))的拉普拉斯譜確定性,為了證明這個(gè)結(jié)論,先證明引理9.

圖3　雙圈圖H(n;n1)

引理9二部雙圈圖H(n;n1)是DLS圖.

證明令G=H(n;n1),設(shè)G′是與G拉普拉斯同譜的圖.并設(shè)G′度為i的點(diǎn)恰有x′i個(gè),i=1,2,…,Δ,其中,Δ為G′的最大度.由引理2

可知

從而有

解得x′1=1,x′2=n-3,x′3=1,x′4=1,故圖G′的度序列為(11,2n-3,31,41),因此,圖G′與圖H(n;n1)同構(gòu).

從而有

解得x′1=0,x′2=n,x′3=-2,x′4=2,顯然這是不可能的.

綜上所述,H(n;n1)是DLS圖.

定理1當(dāng)n≥6,r為任意非負(fù)整數(shù)時(shí),H(n;n1)∨Kr是DLS圖.

5圖H(n;n1,n2)∨Kr是DLS圖

研究二部雙圈圖H(n;n1,n2)(圖4)與完全圖Kr并接后所得圖H(n;n1,n2)∨Kr(其中r為任意非負(fù)整數(shù))的拉普拉斯譜確定性,為了證明這個(gè)結(jié)論,先證明引理10和引理11.

圖4　雙圈圖H(n;n1,n2)

引理102個(gè)形如H(n;n1,n2)的二部雙圈圖,如果具有相同的拉普拉斯譜,則它們必定同構(gòu).

若F∈F22,分以下兩種情況討論.

情形1u或v不在F的同一分支中.

此時(shí),γ(F)=(1+n1)(4+n2)或γ(F)=(4+n1)(1+n2)

這樣的生成森林共有2個(gè),上述每種情況各1個(gè).

子情形1.2u(或v)只與{w,s,t}中的1個(gè)點(diǎn)在F的同一分支中.

此時(shí),γ(F)=(2+n1)(3+n2)或γ(F)=(3+n1)(2+n2)

這樣的生成森林共有6個(gè),上述每種情況各3個(gè).

情形2u和v在F的同一分支中,即u與v同時(shí)和{w,s,t}中的2個(gè)點(diǎn)在F的同一分支中.

此時(shí),γ(F)=1×(4+n1+n2).不難看出,這樣的生成森林共有12個(gè).所以

(1+n2)+3×(2+n1)(3+n2)+

3×(3+n1)(2+n2)+12×(4+n1+n2)

綜上

n2)2+60(n1+n2)-40n1n2+92

同理

由于n1+n2=n′1+n′2,故有n1n2=n′1n′2,從而有n1=n′1,n2=n′2或n1=n′2,n2=n′1

無論哪一種情況,G與G′均同構(gòu).

引理11二部雙圈圖H(n;n1,n2)是DLS圖.

證明令圖G=H(n;n1,n2),設(shè)G′是與G拉普拉斯同譜的圖.并設(shè)G′度為i的點(diǎn)恰有x′i個(gè),i=1,2,…,Δ,其中,Δ為G′的最大度.由引理2

可知

所以,Δ≤5.由引理7可知

或

從而有

解得x′1=2,x′2=n-4,x′3=0,x′4=2,x′5=0,故圖G′的度序列為(12,2n-4,42),因此,圖G′與圖H(n;n1,n2)同構(gòu).

從而有

解得x′1=1,x′2=n-1,x′3=-3,x′4=3,x′5=0,顯然這是不可能的.

綜上所述,H(n;n1,n2)是DLS圖.

定理2當(dāng)n≥6,r為任意非負(fù)整數(shù)時(shí),H(n;n1,n2)∨Kr是DLS圖.

6圖B(n;n1,n2)∨Kr是DLS圖

研究二部雙圈圖B(n;n1,n2)(圖5)與完全圖Kr并接后所得圖B(n;n1,n2)∨Kr(其中r為任意非負(fù)整數(shù))的拉普拉斯譜確定性,為了證明這個(gè)結(jié)論,先證明引理12和引理13.

引理122個(gè)形如B(n;n1,n2)的二部雙圈圖,如果具有相同的拉普拉斯譜,則它們必定同構(gòu).

圖5　雙圈圖B(n;n1,n2)

若F∈F22,分以下兩種情況討論.

情形1u或v不在F的同一分支中.

此時(shí),γ(F)=1×(4+n1+n2)或γ(F)=4×(1+n1+n2)

這樣的生成森林共有2個(gè),上述每種情況各1個(gè).

子情形1.2u或v只與{w,s,t}中的1個(gè)點(diǎn)在F的同一分支中.

此時(shí),γ(F)=2×(3+n1+n2)或γ(F)=3×(2+n1+n2)

這樣的生成森林共有6個(gè),上述每種情況各3個(gè).

情形2u和v在F的同一分支中,即u與v同時(shí)和{w,s,t}中的2個(gè)點(diǎn)在F的同一分支中.

此時(shí),γ(F)=1×(4+n1+n2).不難看出,這樣的生成森林共有12個(gè).所以

綜上

n2)2+60(n1+n2)-48n1n2+92

同理

由于n1+n2=n′1+n′2,故有n1n2=n′1n′2,從而有n1=n′1,n2=n′2或n1=n′2,n2=n′1

無論哪一種情況,G與G′均同構(gòu).

引理13二部雙圈圖B(n;n1,n2)是DLS圖.

證明令圖G=B(n;n1,n2),設(shè)G′是與G拉普拉斯同譜的圖.并設(shè)G′度為i的點(diǎn)恰有x′i個(gè),i=1,2,…,Δ,其中,Δ為G′的最大度.由引理2

可知

所以,Δ≤5.由引理7可知

或

從而有

解得x′1=2,x′2=n-4,x′3=1,x′4=0,x′5=1,故圖G′的度序列為(12,2n-4,31,51),因此,圖G′與圖B(n;n1,n2)同構(gòu).

從而有

解得x′1=1,x′2=n-1,x′3=-2,x′4=1,x′5=1;或x′1=0,x′2=n+3,x′3=-8,x′4=5,x′5=0.顯然這都是不可能的.

綜上所述,B(n;n1,n2)是DLS圖.

定理3當(dāng)n≥6,r為任意非負(fù)整數(shù)時(shí),B(n;n1,n2)∨Kr是DLS圖.

參考文獻(xiàn)：

[1]VON COLLATZ L,SINOGOWITZ U.Spektren endlicher grafen[J].Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg,1957,21(1):63-77.

[2]KAC M.Can one hear the shape of a drum[J].The Americam Mathmatical Monthly,1966,73(4):1-23.

[3]VAN DAM E R,HAEMERS W H.Which graphs are determined by their spectrum?[J].Linear Algebra and its Applications,2003,373(1):241-272.

[4]WANG W,XU C X.On the spectral characterization of T-shape trees[J].Linear Algebra and its Applications,2006,414(2/3):492-501.

[5]LIU X G,ZHANG Y P,LU P L.One special double star like graph is determined by its Laplacian spectrum[J].Applied Mathematics Letters,2009,22(4):435-438.[6]WANG J F,HUANG Q X,BELARDO F,et al.On the spectral characterizations of-graph[J].Discrete Mathematics,2010,310(13/14):1854-1855.[7]LIU F J,HUANG Q X.Laplacian spectral characterization of 3-rose graphs[J].Linear Algebra and its Applications,2013,439(10):2914-2920.

[8]HAEMERS W H,LIU X G,ZHANG Y P.Spectral characterizations of lollipop graphs[J].Linear Algebra and its Applications,2008,428(11/12):2415-2423.

[9]BOULET R.Spectral characterizations of sun graphs and broken sun graphs[J].Discrete Mathematics and Theoretical Computer Science,2009,11(2):149-160.

[10]LU P L,LIU X G,YUAN Z T,et al.Spectral characterizations of sandglass graphs[J].Applied Mathematics Letters,2009,22(8):1225-1230.[11]徐麗珍,何常香.雙圈圖的無符號(hào)拉普拉斯特征多項(xiàng)式的系數(shù)[J].上海理工大學(xué)學(xué)報(bào),2014,36 (1):12-14.

[12]婁源源,吳寶豐.關(guān)于H-聯(lián)圖的拉普拉斯特征值[J].上海理工大學(xué)學(xué)報(bào),2015,37(2):130-135.

[13]LI J S,ZHANG X D.On the Laplacian eigenvalues of a graph[J].Linear Algebra and its Applications,1998,285(1/2/3):305-307.

[15]KELMANS A K,CHELNOLOV V M.A certain polynomial of a graph and graphs with an extremal number of trees[J].Journal Combinatorial Theory,Series B,1974,16(3):197-214.

[16]ZHOU J,BU C J.Laplacian spectral characterization of some graphs obtained by product operation[J].Discrete Mathematics,2012,312(10):1591-1595.

(編輯:石瑛)

Some Graphs Determined by Their Laplacian Spectrum

WANG Yujie,HE Changxiang

(College of Science,University of Shanghai for Science and Technology,Shanghai 200093,China)

Abstract：A graph is said to be determined by its Laplacian spectrum,if there is no other non-isomorphic graph with the same Laplacian spectrum.Three types of bicyclic bipartite graphs H(n;n1),H(n;n1,n2) and B(n;n1,n2),which all have the base of B(P3,P3,P3) (three disjoint paths of length 2 between two vertices) were studlied.It is proved that the graphs are determined by their Laplacian spectrum,and the graphs obtained by the join of complete graphs and the above three type bicyclic graphs are also determined by their Laplacian spectrum.

Keywords：bipartite bicyclic graph; Laplacian matrix; determination by the Laplacian spectrum

文章編號(hào)：1007-6735(2016)03-0223-07

DOI：10.13255/j.cnki.jusst.2016.03.004

收稿日期：2015-12-30

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(11201303);上海市自然科學(xué)基金資助項(xiàng)目(12ZR1420300)

通信作者：何常香(1979-),女,副教授.研究方向:組合數(shù)學(xué)與圖論.E-mail:changxianghe@hotmail.com

中圖分類號(hào)：O 157.5

文獻(xiàn)標(biāo)志碼：A

第一作者： 王玉潔(1991-),女,碩士研究生.研究方向:組合數(shù)學(xué)與圖論.E-mail:569971787@qq.com