張海東

(蘭州交通大學(xué)數(shù)理學(xué)院 甘肅 蘭州 730070)

0 引言

本文考慮的圖均為簡單無向連通圖。設(shè)圖G的頂點(diǎn)集為V(G)={v1,v2,…,vn}，邊集為E(G)={e1,e2,…,en}。若圖G中兩個(gè)頂點(diǎn)vi與vj相鄰，則記為vivj，并用di表示頂點(diǎn)vi的度，也即是與vi相鄰頂點(diǎn)的數(shù)目。設(shè)圖G的鄰接矩陣為A(G)=(aij)n×n，其中當(dāng)vivj∈E(G)時(shí)，aij=1；否則aij=0。

記圖G的關(guān)聯(lián)矩陣為B(G)=(bij)n×m，其中

并將B(G)的轉(zhuǎn)置記為B(G)T，易得圖G的規(guī)范的無符號(hào)拉普拉斯矩陣Q(G)滿足[5]

=In(G)+R(G)

(1)

其中In為n階的單位矩陣。

剖分圖S(G)是在圖G的每條邊插入一個(gè)新頂點(diǎn)所得到的圖。顯然，S(G)是一個(gè)二部圖，因此，V(S(G))=V1∪V(G)，其中V1是新插入的度為2的頂點(diǎn)集。

1 主要結(jié)果

定義1[6]友誼圖Fn是將3長圈C3的n次復(fù)制收縮在一個(gè)公共頂點(diǎn)所得(如圖1)，其中n是任意正整數(shù)。顯然，F(xiàn)n的頂點(diǎn)數(shù)和邊數(shù)分別為2n+1和3n。

圖1 友誼圖

圖2 荷蘭風(fēng)車圖

RP(Km,n,λ)=λm+n-2(λ2-1)

引理5[7]若M是一個(gè)非奇異方陣，則

則

R(S(Kn))

證明易知S(Km,n)的頂點(diǎn)數(shù)為mn+m+n，并且S(Km,n)的度對角矩陣D(S(Km,n))和鄰接矩陣A(S(Km,n))分別為

則

R(S(Km,n))

det(λImn+m+n-R(S(Km,n)))

det(λImn+m+n-R(S(Km,n)))

證明易知S(Fn)的頂點(diǎn)數(shù)為5n+1，并且S(Fn)的度對角矩陣D(S(Fn))和鄰接矩陣A(S(Fn))分別為

則

R(S(Fn))

det(λI5n+1-R(S(Fn)))

det(λI5n+1-R(S(Fn)))

則

2 結(jié)語