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

劉 群

(河西學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 張掖 734000)

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

劉 群

(河西學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 張掖 734000)

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

圖的譜;共譜圖;特征值

0 引言

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

(c)頂點(diǎn)度的平方和。

引理1.2［3，4］設(shè)圖G是一個(gè)點(diǎn)集和邊集都不為空集的圖，則

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

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

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

證明:設(shè)圖G'與圖G(Cq，Cq，Pr)相關(guān)于Laplacian矩陣同譜，則根據(jù)引理2.1

和引理2.1(a)，它們有相同數(shù)目的點(diǎn)數(shù)、邊數(shù)和連通分支數(shù)，即圖G'有2q－2+r個(gè)點(diǎn)和2q－1+r條邊，并且它是連通的，由引理2.2可得4≤μ1≤4.8，因此圖G'沒有度數(shù)大于3的點(diǎn)。設(shè)圖G'中有度為i的點(diǎn)ni個(gè)，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確定的。

對(duì)于一個(gè)圖來(lái)說(shuō)，它的Laplacian特征值確定了它的補(bǔ)圖的Laplacian特征值，因此顯然有下面的結(jié)論:

推論2.3圖G(Cq，Cq，Pr)的補(bǔ)圖是由它的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-)，女，甘肅張掖人，講師，碩士研究生，主要從事代數(shù)圖論方面的研究。

責(zé)任編輯:程艷艷