圖H(p，pK16）的拉普拉斯譜刻畫

趙紹玉

（三明學院 信息工程學院，福建 三明 365004）

這里考慮的都是有限、無向、連通的簡單圖，取V（G),E（G),ni（G)分別表示圖G的頂點集、邊集和度為 i頂點數(shù)。圖 G 的鄰接矩陣 A（G)=（aij）n×n,，其中 aij是 1當且僅當 vi和 vj相鄰，否則是 0。用 di表示圖 G 中的頂點 vi的度數(shù)。D（G）=diag（d1，d2，…，dn)是由頂點的度構成的對角矩陣。矩陣 L（G）=D（G）-A（G）稱為圖 G 的 Laplacian 矩陣。多項式 P(A（G);λ)=det（λIn-A（G)）=λn+a1λn-1+…+an,稱為圖G 的鄰接特征多項式,P(L（G);μ)=det（μIn-L（G)）=μn+b1μn-1+…+bn稱為圖 G 的 Laplacian 特征多項式，In是單位矩陣。設 λi（i=1，……，n）是 A（G)的特征值,它們的集合構成了圖 G 的鄰接譜;μi（i=1，……，n）是L（G)的特征值，它們構成的集合稱為圖G的Laplacian譜。若兩個圖的鄰接譜(Laplacian譜)相同，就說它們是鄰接(Laplacian)同譜圖。同樣,若兩個圖的Laplacian譜相同，則說它們是Laplacian同譜圖。與圖G鄰接同譜的圖都與G同構，稱圖G可由其鄰接譜確定。與圖Laplacian同譜的圖都與同構，稱圖可由其Laplacian譜確定。圖譜的確定問題，最早由Günthard和Primas提出[1],起初主要用于化學方面的研究;直到2003年,這一問題再次被Van Dam和Haemers提出[2],才引起了廣泛的關注,得到了很多研究成果[3-11]。用H（p，tK1，m）表示具有tm+p個頂點的單圈圖,它是由圈Cp連續(xù)相鄰的t（1≤t≤p）個頂點分別與星 K1，m的中心重合而得到的。當 t=1 時，盧鵬麗[4]證明了章魚圖 H（p，tK1，m）是由它的拉普拉斯譜確定的;Bu C J等[5]證明了H（p，pK1，2）是拉普拉斯譜確定的;王陸華[6]證明了圖H（p，（p-1）K1，2）是拉普拉斯譜確定的，特別當 p 為偶數(shù)時，圖 H（p，2K1，2），H（p，3K1，2），H（p，（p-3）K1，2），H（p，（p-2）K1，2）也都是由其拉普拉斯譜確定。梅若星等[7]證明了單圈圖 H（p，pK1，3），H（p，pK1，4）和 H（p，（p-1）K1，3）分別是由其拉普拉斯譜確定的。并且當 p 為偶數(shù)時，H（p，2K1，3），H（p，（p-3）K1，3）和H（p，（p-2）K1，3）也分別由其拉普拉斯譜確定。孫秋實等[8]證明了單圈圖 H（p，pK1，5）和 H（p，（p-1）K1，4）是由其拉普拉斯譜確定的，而且當 p 為偶數(shù)時，H（p，2K1，4），H（p，（p-3）K1，4）和 H（p，（p-2）K1，4）也分別由其拉普拉斯譜確定。

前述這些論文，只是研究了單圈圖 H（p，pK1，m）（1≤m≤5）的拉普拉斯譜確定情況，而對于更復雜、更一般單圈圖H（p，pK1，m）（6≤m）的拉普拉斯譜確定問題未見報道，所以，本文繼續(xù)研究了單圈圖 H（p，pK1，m）（m≥6）的拉普拉斯譜確定問題，證明了單圈圖 H（p，pK1，6）是由其拉普拉斯譜確定的。

1 基本引理

引理1[3]若圖G和圖H是拉普拉斯同譜圖,則

(1)圖G和圖H具有相同的頂點數(shù)和邊數(shù)；

(2)圖G和圖H頂點度的平方和相等。

引理2[9]設圖G是一個含有圈Ck的連通單圈圖。若圖G和圖G'是拉普拉斯同譜的，則圖G'也是一個與圖G具有相同頂點數(shù)和邊數(shù)、含有圈Ck的連通單圈圖，并且

引理3[10]非空集合E（G）、V（G）分別表示圖G的頂點集和邊集，則有

其中Δ是圖G的最大的頂點度，mi表示圖G中與頂點vi鄰接的頂點的度數(shù)的平均值。

引理4[11]設ni圖G有n個頂點，是它的補圖，則

2 主要結果

本節(jié)證明了單圈圖是由其拉普拉斯譜確定的，并推出它的補圖也是由其拉普拉斯譜確定的。

定理 1圖 H（p，pK1，6）是由其拉普拉斯譜確定的。

證明令G=H（p，pK1，6）,假設圖G'和圖G具有相同的拉普拉斯譜，則由引理1可知,圖G'是一個具有7p個頂點7p條邊且含有圈Cp的連通單圈圖。由引理3得

所以Δ≤9。設是圖G中度為i的頂點個數(shù)。由引理1和引理2知

由此推出

因為 n8，n9≥0為整數(shù)且 p為大于等于 3的任意整數(shù)，令 p=3，由（10）可得 n9=0，n8≤p，將 n9=0代入（9）可得

由（2）和（11）得 70p≤20n7+70n8≤4n5+15n6+36n7+70n8≤70p

由此可得 4n5+15n6+16n7≤0，又因為 n5，n6，n7為大于等于 0的整數(shù)，所以 n5=n6=n7=0，將 n7=0代入（11）可得 n8≥p，所以 n8=p。進而可解得 n2=n3=n4=0，n1=6p。所以圖 G'的序列 d（G'）=（8p，16p）。因為具有刻度序列（8p，16p）且 含有 Cp的連通單圈圖只能是形如圖 H（p，pK1，6）的圖，所以 G'≌G。因此單圈圖 H（p，pK1，6）是由其拉斯拉普譜確定的。

推論1圖H（p，pK1，6）的補圖可由其拉普拉斯譜確定的。

證明由引理4可知，圖H（p，pK1，6）的補圖也可由其拉普拉斯譜確定。

3 結論

本文利用Laplacian同譜圖的一些性質(zhì)，通過對同譜圖頂點的度數(shù)進行討論，證明了單圈圖H（p，pK1，6）是由其 Laplacian 譜確定的，進一步補充了對單圈圖 H（p，pK1，m）的研究，具有一定的理論價值，但是對于一般形式單圈圖H（p，pK1，m）的Laplacian譜確定問題還沒有解決，有待繼續(xù)研究。