一類雙圈圖拉普拉斯譜刻畫

劉 群

(河西學院 數學與統計學院，甘肅 張掖 734000)

一類雙圈圖拉普拉斯譜刻畫

劉 群

(河西學院 數學與統計學院，甘肅 張掖 734000)

稱圖是由譜確定的，如果沒有非同構的圖具有相同的譜。用Cq標記長度為q的圈。圈圖Cq的一個頂點與路圖Pr的一個懸掛點相連，圈圖Cq的一個頂點與Pr的另一個懸掛點相連，所得的圖稱為G(Cq，Cq，Pr)。本文將證明圖 G(Cq，Cq，Pr)由它的 Laplacian譜確定。

圖的譜;共譜圖;特征值

0 引言

設圖 G=(V(G)，E(G))是點集為 V(G)={v1，v2，v3，...，vn}，邊集為 E(G)的圖。本文涉及到所有圖均為簡單的無向圖。設A(G)圖G的(0，1)－鄰接矩陣，dk是點vk的度數。稱矩陣L(G)=D(G)－A(G)為圖G的Laplacian矩陣，其中D(G)是對角元素為{d1，d2，...，dn}的n×n階對角矩陣，記多項式P(L(G))=det(μI－L(G))為圖G 的Laplacian特征多項式，I為單位矩陣。令 P(L(G))=q0μn+q1μn－1+…… +qn，其中q0，q1，...，qn是多項式的系數。因為矩陣L(G)是實對稱矩陣，因此它的特征值都是實數。設μ1≥μ2≥……≥μn(=0)是圖的Laplacian特征值。圖G的Laplacian譜是由圖G的Laplacian特征值(帶重數)組成的。如果兩個圖具有相同的譜，那么稱這兩個圖是共譜的很明顯，如果兩個圖是共譜的，那么它們具有相同的點數。對于圖G，如果沒有非同構的圖與它相關于Laplacian共譜，則稱圖G是由Laplacian譜確定的。

在圖譜理論中，哪些圖是由圖譜確定的這一問題似乎是一個比較難的問題。

截止目前，只有少數圖被證明有它的譜確定。本文將討論G(Cq，Cq，Pr)的拉普拉斯譜確定問題，其中G(Cq，Cq，Pr)是指圈圖Cq的一個頂點與路圖Pr的一個懸掛點相連，圈圖Cq的一個頂點與Pr的另一個懸掛點相連。顯然它是一個具有2q－2+r個頂點和2q－1+r條邊的雙圈圖。

1 預備知識

引理1.1［1，2］(1)設圖G是一個具有n個點和m條邊的圖，并設d=(d1，d2，…dn)點的不增的度序列，則多項式的一些系數滿足:

其中m是圖G的邊數，S(G)是圖G的支撐樹的數目。

(2)對于Laplacian矩陣，根據它的譜我們可以得到:

(a)圖G的連通分支數;

(b)圖G的生成樹的數目。

(c)頂點度的平方和。

引理1.2［3，4］設圖G是一個點集和邊集都不為空集的圖，則

其中Δ(G)是圖G中點的度數的最大值，μ1是圖G的最大Laplacian特征值，mu是圖G中相鄰于點u的度數的平均值。

2 圖G(Cq，Cq，Pr)是由它的Laplacian譜確定的

定理2.1圖G(Cq，Cq，Pr)是由它的Laplacian譜確定。

證明:設圖G'與圖G(Cq，Cq，Pr)相關于Laplacian矩陣同譜，則根據引理2.1

和引理2.1(a)，它們有相同數目的點數、邊數和連通分支數，即圖G'有2q－2+r個點和2q－1+r條邊，并且它是連通的，由引理2.2可得4≤μ1≤4.8，因此圖G'沒有度數大于3的點。設圖G'中有度為i的點ni個，i=1，2，...，△'，Δ'≤3 是 G'的最大度，則

若 Δ'≤2，則 n2=2q+r，n1= －2 ＜0 矛盾，因此 Δ'=3，得 n1=0，n2=2q+r－4，因此，G'是圖1 或圖2:

圖 1 θ(a，b，c)

圖 2 G(Ct，Cs，Ph)

若 G'=θ(a，b，c)，則 a+b+c－1=2q －2+r，ab+ac+bc=q2，解得 a∈φ，b∈φ，c∈φ 矛盾。

若 G'=G(Ct，Cs，Ph)，則 ts=q2，解得 t=q=s，故 G?G'。

定理2.2圖G(Cq，Cq，Pr)是由它的Laplacian確定的。

對于一個圖來說，它的Laplacian特征值確定了它的補圖的Laplacian特征值，因此顯然有下面的結論:

推論2.3圖G(Cq，Cq，Pr)的補圖是由它的Lacplacian譜確定的。

［1］ E R van Dam，W H Haemers.Which graphs are determined by their spectrum［J］.Linear Algebra Appl，2003(373):241 －272.

［2］ C S Oliveira，N M M de Abreu，S Jurkiewilz，The characteristic polynomial of the Laplacian of graphs in(a，b)-linear cases［J］.Linear Algebra Appl，2002(365):113 －121.

［3］ A K Kelmans，V M Chelnokov.A certain polynomial of a graph and graphs with an extremal number of trees［J］.Combin.Theory，Ser.B，1974(16):197－214.

［4］ J-S Li，X-D Zhang，On the Laplacian eigenvalues of a graph［J］.Linear Algebra Appl，1998(285):305 －307.

Laplacian Spectrum Characterization of a Class of Bicyclic Graphs

LIU Qun

(School of Mathematics and Statistics，Hexi University，Zhangye 734000，China)

A graph G is determined by Laplacian spectrum if there is no other non-isomorphic graph with the same Laplacian spectrum.Cqdenotes the cycle with the length of q.G(Cq，Cq，Pr)is a graph consisting of two vertex-disjoints of cycle Cqand Prjoined by a path.This paper shows that graph G(Cq，Cq，Pr)is determined by its Laplacian spectrum.

spectrum of a graph;cospectral graphs;eigenvalue

O157.5

A

1009－3907(2012)08－0989－03

2012-04-20

劉群(1979-)，女，甘肅張掖人，講師，碩士研究生，主要從事代數圖論方面的研究。

責任編輯:程艷艷