圖的規范化Laplace和規范化無符號Laplace特征多項式

陳丹丹, 馬小玲

(新疆大學 數學與系統科學學院, 烏魯木齊 830046)

1 引言與預備知識

2 規范化Laplace和規范化無符號Laplace特征多項式

定理1設G是有n個頂點的圖, 則圖G的規范化Laplace矩陣的特征多項式為

則

根據行列式的性質, 可得

(1)

將式(1)的每個行列式分解為兩個行列式之和并繼續該過程, 直到第n次可得

其中I表示對應頂點個數的單位矩陣,vi1,vi2,…,vik是從n個頂點中任意取出k個頂點, 且滿足1≤i1

定理2設圖G有n個頂點, 則圖G的規范化無符號Laplace矩陣的特征多項式為

證明: 類似于定理1的證明, 有

根據行列式的性質, 可得

(2)

將式(2)的每個行列式分解為兩個行列式之和并繼續該過程, 直到第n次可得

其中I表示對應頂點個數的單位矩陣,vi1,vi2,…,vik是從n個頂點中任意取出k個頂點, 且滿足1≤i1

3 矩陣的特征多項式

定理3設G是沒有孤立點的圖, 其頂點集為V={v1,v2,…,vn},S是圖G的頂點子集, 則

證明: 設A(G)=(aij)(1≤i,j≤n)是圖G的鄰接矩陣, 則有

根據行列式的性質, 把上述行列式表示為兩個行列式之和, 即

(3)

對式(3)中的每個行列式繼續上述操作, 直到第n次可得

其中I表示對應頂點個數的單位矩陣,vi1,vi2,…,vik是從n個頂點中任意取出k個頂點, 且滿足1≤i1

對于正則圖, 根據定理3易得如下推論.

推論1若圖G是n個頂點的r-正則圖, 則

4 正則圖的規范化Laplace和規范化無符號Laplace特征多項式

下面用圖的鄰接矩陣的特征多項式給出正則圖的規范化Laplace和規范化無符號Laplace特征多項式的一般表達式.

定理4若圖G是n個頂點的r-正則圖, 則其規范化Laplace特征多項式為

證明: 設A(G)=(aij)(1≤i,j≤n)是圖G的鄰接矩陣.因為G是r-正則圖, 并且R(G)=D-1/2(G)A(G)D-1/2(G), 則由L(G)=I-R(G), 可知

所以

(4)

根據行列式的性質, 將式(4)中的行列式表示為兩個行列式之和為

(5)

將式(5)中的每個行列式分別表示為兩個行列式之和并繼續該過程, 直到第n次可得

其中I表示對應頂點個數的單位矩陣,vi1,vi2,…,vik是從n個頂點中任意取出k個頂點, 且滿足1≤i1

根據圖G的規范化無符號Laplace矩陣的定義并類似于定理4的證明思想, 可得如下定理, 即圖G規范化無符號Laplace特征多項式的一般表達式.

定理5設圖G是n個頂點的r-正則圖, 則其規范化無符號Laplace特征多項式為

5 Middle圖的鄰接特征多項式

引理1[12]設G是有n個頂點、m條邊的圖,L(G)是圖G的線圖, 則其特征多項式為

(6)

定理6設圖G有n個頂點和m條邊, 則其Middle圖M(G)的特征多項式為

證明: 若圖G有n個頂點和m條邊, 則由文獻[1]中定理2.4.6可知,

(7)

由式(6)可得

(8)

將式(8)代入式(7)可得結果.證畢.