聯圖的Normalized Laplace特征多項式

廖麗雯,陳海燕(集美大學理學院,福建廈門361021)

?

聯圖的Normalized Laplace特征多項式

廖麗雯,陳海燕*
(集美大學理學院,福建廈門361021)

摘要:利用代數方法得到了兩個正則圖聯圖的Normalized Laplace特征多項式的一個表達式,在此基礎上得到了正則圖聯圖的Normalized Laplace特征值與其因子圖對應特征值之間的關系式.計算了一些特殊圖的度基爾霍夫指標.

關鍵詞:聯圖;Normalized Laplace多項式;度基爾霍夫指標

設G是一個n個頂點的簡單圖,它的頂點集為{1,2,…,n},則G的鄰接矩陣是一個(0,1)矩陣,記為A=(aij)n×n,其中

圖G的Normalized Laplace矩陣和圖G上的隨機游動有緊密的聯系,它的許多性質已被人們所熟知,如

1)L是半正定矩陣;

2)0是L的特征值,且它的所有特征值位于閉區間[0,2].

其他更多性質可參見文獻[1].

設圖G鄰接矩陣特征值與Normalized Laplace特征值分別為λ1≥λ2≥…≥λn,0≤λ'2≤…≤λ'n.如果G為r-正則圖,則由定義直接可得:

但如果G不是正則圖,λi和λ'i之間就沒有必然的聯系.本文我們主要考慮兩個圖聯圖的Normalized Laplace特征值與其因子圖Normalized Laplace特征值的關系.首先我們給出聯圖的定義.

定義1[2]設H與G是兩個簡單連通圖,則它們的聯圖記為H?G,是指頂點集為V(H)∪V(G),邊集為E(H)∪E(G)∪{uv|u∈V(H),v∈V(G)}的圖.

下面我們用χ(G;x)表示圖G的Normalized Laplace特征多項式,則

在第二部分,首先用代數方法得到了兩個正則圖聯圖的Normalized Laplace多項式的一個表達式,然后在此基礎上得到了兩個正則圖聯圖的Normalized Laplace特征值和其兩個因子圖Normalized Laplace特征值之間的關系式.第三部分作為應用,得到了一些特殊圖的度基爾霍夫指標的表達式.

1 正則圖聯圖的Normalized Laplace多項式

為了討論正則圖聯圖的Normalized Laplace特征多項式,需要下面的已知結論:

引……