聯(lián)圖的Normalized Laplace特征多項式

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

?

聯(lián)圖的Normalized Laplace特征多項式

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

摘要:利用代數(shù)方法得到了兩個正則圖聯(lián)圖的Normalized Laplace特征多項式的一個表達式,在此基礎(chǔ)上得到了正則圖聯(lián)圖的Normalized Laplace特征值與其因子圖對應(yīng)特征值之間的關(guān)系式.計算了一些特殊圖的度基爾霍夫指標(biāo).

關(guān)鍵詞:聯(lián)圖;Normalized Laplace多項式;度基爾霍夫指標(biāo)

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

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

1)L是半正定矩陣;

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

其他更多性質(zhì)可參見文獻[1].

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

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

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

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

在第二部分,首先用代數(shù)方法得到了兩個正則圖聯(lián)圖的Normalized Laplace多項式的一個表達式,然后在此基礎(chǔ)上得到了兩個正則圖聯(lián)圖的Normalized Laplace特征值和其兩個因子圖Normalized Laplace特征值之間的關(guān)系式.第三部分作為應(yīng)用,得到了一些特殊圖的度基爾霍夫指標(biāo)的表達式.

1 正則圖聯(lián)圖的Normalized Laplace多項式

為了討論正則圖聯(lián)圖的Normalized Laplace特征多項式,需要下面的已知結(jié)論:

引理1[3]設(shè)A,B是兩個n階對稱矩陣,若AB=BA,則存在可逆矩陣P,使得

這里λi,βi分別表示A,B的特征值,即

定理1 設(shè)G1,G2是兩個正則圖,頂點數(shù)分別為n1,n2,正則度分別為r1,r2.則聯(lián)圖G1?G2的Normalized Laplace特征多項式為:

這里r1≥λ2≥…≥λn1,r2≥μ2≥…≥μn2分別是G1和G2鄰接矩陣的特征值.

證明 用A1,A2分別表示G1,G2的鄰接矩陣,則由聯(lián)圖的定義可得G1?G2的鄰接矩陣和度對角矩陣可分別表示為:

所以

從而可得

由于G1是r1正則圖,所以Jn2×n1A1=r1Jn2×n1.把上面的行列式第一行左乘矩陣

加到第二行可得

這里

設(shè)A1的特征值為r1≥λ2≥…≥λn1,則顯然有

又G2是r2正則圖,A2Jn2×n2=Jn2×n2A2=r2Jn2×n2,若設(shè)r2≥μ2≥…≥μn2為A2的特征值,Jn2×n2的特征值為n2,0,…,0,則由引理1可得:

由上得G1?G2的Normalized Laplace特征多項式為:

由上面的定理,我們很容易由G1,G2的鄰接矩陣特征值得到G1?G2的Normalized Laplace特征值:

再由正則圖的鄰接矩陣特征值和其Normalized Laplace特征值之間的關(guān)系(1),我們馬上可以得到下面的定理.

定理2 設(shè)G1,G2是兩個正則圖,頂點數(shù)分別為n1,n2,正則度分別為r1,r2.若G1的Normalized Laplace特征值為0≤λ'2≤…≤λ'n1;G2的Normalized Laplace特征值為0≤μ'2≤…≤μ'n2,則聯(lián)圖G1?G2的Normalized Laplace特征值為:

這里G1,G2是正則圖,并不能保證G1?G2是正則圖,除非r1+n2=r2+n1,所以定理2的結(jié)果并不能通過式(1)由G1?G2鄰接特征值與G1和G2鄰接特征值的關(guān)系得到.

推論1 設(shè)G1,G2是兩個正則圖.若1作為它們Normalized Laplace特征值的重數(shù)分別為m1,m2,則1作為G1?G2的Normalized Laplace特征值的重數(shù)為m1+m2.

在定理1中,若特別取其中一個圖為空圖?Km或完全圖Km,由于?Km的正則度和所有特征值都為0, 而Km是m-1正則,特征值為m-1,-1,-1,…, -1,所以可以得到下面更具體的結(jié)果.

推論2 設(shè)圖G是n個頂點的r正則圖,則

這里r≥λ2≥…≥λn是G的鄰接矩陣特征值.所以?Km?G的Normalized Laplace特征值為:

推論3 設(shè)圖G是n個頂點的r正則圖,則

χ(Km?G;x)=

這里r≥λ2≥…≥λn是G的鄰接矩陣特征值.所以Km?G的Normalized Laplace特征值為:

2　應(yīng) 用

設(shè)G是一個簡單連通圖,若G的每條邊看作電阻值為1的電阻,則G就可以看作是一個電網(wǎng)絡(luò).Klein 和Randic在文獻[4]中把圖G上兩點i,j之間的電阻距離定義為它們之間的等效電阻值,記為rij,而G中所有點對之間的電阻距離之和,即Kf(G)稱為圖G的基爾霍夫指標(biāo).而最近,Chen等在文獻[5]中定義了度基爾霍夫指標(biāo):并發(fā)現(xiàn)Kf*(G)和圖的Normalized Laplace特征值有如下的關(guān)系式.

引理2[5]設(shè)圖G=(V(G),E(G)),其中|V(G)| =v,|E(G)|=e,則有

其中σ2≥σ3≥…≥σn是G的非零Normalized Laplace特征值.

由上面的引理和式(2),馬上可得到兩個正則圖聯(lián)圖的度基爾霍夫指標(biāo)的一個表達式.

定理3 設(shè)G1,G2是兩個正則圖,頂點數(shù)分別為n1,n2,正則度分別為r1,r2.則

這里r1≥λ2≥…≥λn1,r2≥μ2≥…≥μn2分別是G1和G2鄰接矩陣的特征值.

特別地,若G是一個正則圖,則它的錐圖(K1?G)和雙錐圖(?K2?G)的度基爾霍夫指標(biāo)有如下結(jié)果.

定理4 設(shè)G是n個頂點r-正則的圖,則這里r≥λ2≥…≥λn是G的鄰接矩陣特征值.

這里r≥λ2≥…≥λn是G的鄰接矩陣特征值.

最后我們給出幾類常見正則圖聯(lián)圖的度基爾霍夫指標(biāo).

例1 圖?Km?Kn的度基爾霍夫指標(biāo).

因為?Km的正則度和所有特征值都為0,而Km是m-1正則,特征值為m-1,-1,-1,…,-1的圖,所以由定理3馬上可得:

例2 圖?Km?Cn的度基爾霍夫指標(biāo).

Cn的鄰接矩陣特征值為[6]:

所以由定理3可得

特別對于輪圖,有

例3 圖Km?Cn的度基爾霍夫指標(biāo)

例4 圖Km?O3(O3是Peterson圖)的度基爾霍夫指標(biāo).

Petersen圖的鄰接矩陣特征值為[2]:

3,1,1,1,1,1,-2,-2,-2,-2.

所以

參考文獻:

[1] CHUNG F R K.Spectral graph theory[M].Rhode Island: Amer Math Soc,1997:186-199.

[2] CVETKOVIC'D,ROWLINSON P,SIMIC'S.An introduction to the theory of graph spectra[M].New York: Cambridge University,2010:1-23.

[3] MARCUS M,MINC H.A survey of matrix and matrix inequalities[M].Boston:Allyn and Bacon Inc,1964: 156-167.

[4] KLEIN D J,RANDIC'M.Resistance distance[J].Math Chem,1993,12(1):81-95.

[5] CHEN H Y,ZHANG F J.Resistance distance and the normalized laplacian spectrum[J].Discrete Applied Mathematics,2007,155:654-661.

[6] BIGGS N L.Algebraic graph theory[M].2nd ed.New York:Cambridge University,1993:14-22.

Normalized Laplace Polynomials of Join Graphs

LIAO Liwen,CHEN Haiyan
(School of Sciences,Jimei University,Xiamen 361021,China)

Abstract:Let G1and G2be two regular graphs.In this paper,by using algebraic method,we first obtain an expression of the Normalized Laplace polynomial for the join graph of G1and G2.Then based on this expression,we obtain the relation between the normalized Laplace eigenvalues of the join graph and those of G1and G2.Finally,as applications,we compute the degree Kirchhoff index of several kinds of graphs.

Key words:join graph;normalized laplace polynomial;degree Kirchhoff index

*通信作者:chey5@jmu.edu.cn

收稿日期:2015-05-13 錄用日期:2015-08-26

doi:10.6043/j.issn.0438-0479.2016.02.015

中圖分類號:O 157.1

文獻標(biāo)志碼:A

文章編號:0438-0479(2016)02-0233-04

引文格式:廖麗雯,陳海燕.聯(lián)圖的Normalized Laplace特征多項式[J].廈門大學(xué)學(xué)報(自然科學(xué)版),2016,55(2):233-236.

Citation:LIAO L W,CHEN H Y.Normalized Laplace polynomials of join graphs[J].Journal of Xiamen University(Natural Science),2016,55(2):233-236.(in Chinese)