半正則圖的Estrada指數(shù)的界

張 寧，張海霞，楊斌鑫

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院，太原 030024)

本文基于文獻(xiàn)[1]的結(jié)論和證明方法，通過優(yōu)化簡單圖和二部圖的Estrada指數(shù)的界，得到連通圖和連通二部圖的Estrada指數(shù)的界，得到半正則圖的Estrada指數(shù)的界。最后討論了Estrada指數(shù)的若干應(yīng)用。

1 背景知識

1.1 研究現(xiàn)狀與研究意義

研究現(xiàn)狀：Estrada指數(shù)提出后，引起了數(shù)學(xué)工作者的關(guān)注.研究者試圖通過建立Estrada指數(shù)與圖的結(jié)構(gòu)參數(shù)之間的聯(lián)系，刻畫圖的結(jié)構(gòu)性質(zhì)。本文研究Estrada指數(shù)的界，對界進(jìn)行估計。

研究意義：Estrada指數(shù)應(yīng)用廣泛，具有較高的理論意義和實際價值。

1.2 相關(guān)定義

簡單圖：圖既沒有環(huán)也沒有兩條邊連接同一對頂點(diǎn)。

連通圖：若G只有一個分支，則稱G是連通的。

二部圖：圖的頂點(diǎn)集就是分為兩個子集X和Y，使得任意一條邊都有一個端點(diǎn)在X中，另一個端點(diǎn)在Y中。

k正則圖：若對所有v∈V，有dv=k.

半正則圖:每個頂點(diǎn)的度是r1或r2的二部圖，且任一邊連接的是度為r1和r2的頂點(diǎn)。

(n，m)圖：n個點(diǎn)，m條邊的圖。

鄰接矩陣：表示點(diǎn)與點(diǎn)相鄰關(guān)系的矩陣。

1.3 Estrada指數(shù)的性質(zhì)

A(G)表示G的(0，1)鄰接矩陣[1]，A(G)的特征值，構(gòu)成了G的譜.n個點(diǎn)的圖有n個特征值.圖的特征值定義為λ1，λ2，…λn，并且按遞減序列排列：λ1≥λ2≥…≥λn.

2000年，E.Estrada在文章中最先引入Estrada指數(shù)。定義為:

(1)

稱為Estrada指數(shù)。

(2)

從文獻(xiàn)[2]中，Mk(G)等于G的長為k的圈的數(shù)量。

性質(zhì)2：如果G是二部圖，n0是特征值0的重數(shù)，

(3)

2 一些特殊圖的Estrada指數(shù)的界

文章的前兩個定理的下界，算到三階譜矩。為了提高下界，利用正確的猜想。

猜想1：在n個點(diǎn)的連通圖中，路有極小Estrada指數(shù)。

該猜想是由文獻(xiàn)[3]的作者提出并給出證明。

M4=14+6(n-4).

(4)

2.1 連通圖的Estrada指數(shù)的界

引理1G是一個(n，m)簡單圖。G的Estrada指數(shù)的界是：

等式兩邊成立的條件都是G是一個n個點(diǎn)的空圖。

定理1G是一個(n，m)連通圖，

證明：為了證明該定理，經(jīng)常使用一些已知的(n，m)圖的階矩，

M0=n;M1=0;M2=2m;M3=6t;

M4=14+6(n-4).

交叉項：應(yīng)用算術(shù)幾何平均不等式，

n(n-1)(eM1)2/n=n(n-1).

平方項：利用冪級數(shù)展開式，使用M0，M1，M2，M3，M4，得到:

聯(lián)立兩個結(jié)果，開平方得到:

上界：從等式(2)開始：

2.2 連通二部圖的Estrada指數(shù)的界

引理2[1]G是一個(n，m)二部圖.G的Estrada指數(shù)的界是：

定理2G是一個(n，m)連通二部圖。G的Estrada指數(shù)的界：

下界的證明如定理1，用n+來定義G的正特征值的個數(shù)。二部圖的特征值關(guān)于原點(diǎn)對稱，n0+2n+=n.

上界：

EE=n0+eλ1+e-λ1+eλ2+e-λ2+…+eλn++e-λn+

i=1，2，…n+

3 半正則圖的Estrada指數(shù)的界

3.1 結(jié)果一

引理3[1]G是一個度為r的n個點(diǎn)的正則圖.G的Estrada指數(shù)的界是：

er+

上界：

下界:

平方項：

交叉項：

聯(lián)立這兩個結(jié)果，開平方、移項得到下界。

3.2 結(jié)果二

引理4[1]G是一個度為r的n個點(diǎn)的正則二部圖.G的Estrada指數(shù)的界是：

上界：

下界：

平方項：

交叉項：

(n-2)(n-3)

聯(lián)立以上兩個結(jié)果，開平方、移項得下界。

4 結(jié)束語

本文獲得連通圖和連通二部圖的Estrada指數(shù)的界，并得到二個半正則圖的Estrada指數(shù)的上下界.Estrada指數(shù)應(yīng)用十分廣泛，用于量化長鏈蛋白質(zhì)分子的折疊度[4-6]、提供了一種找到復(fù)雜網(wǎng)絡(luò)核心的手段、拓展的原子分支[7-8]等。