圖的ISI-Estrada指數(shù)的界

李海毓，高玉斌

(中北大學(xué) 理學(xué)院， 太原 030051)

0 引言

拓?fù)渲笖?shù)是一種基于化合物分子圖構(gòu)建的分子描述符，在數(shù)學(xué)與化學(xué)中有著廣泛的應(yīng)用。為了描述小分子和大分子的三維結(jié)構(gòu)，Estrada[1]提出了一種新的基于特征值的拓?fù)渲笖?shù)，稱為Estrada指數(shù)。Estrada指數(shù)在生物、分子化學(xué)、復(fù)雜網(wǎng)絡(luò)等方面都有廣泛的應(yīng)用，是一種重要的分子拓?fù)渲笖?shù)，相關(guān)研究成果可參見文獻(xiàn)[2-7]。

設(shè)G是一個(gè)無環(huán)、無重邊的簡(jiǎn)單無向圖，其頂點(diǎn)集為V(G)={v1,v2,…,vn}，邊集為E(G)，且|E(G)|=m。若vi與vj相鄰， 記為vivj∈E(G)，用di表示頂點(diǎn)vi的度。矩陣的零度是指其零特征值的個(gè)數(shù)，用n0表示矩陣的零度。矩陣的譜半徑是指矩陣的特征值中絕對(duì)值最大的特征值，而圖的譜是指其鄰接矩陣G的所有特征值的集合。設(shè)A(G)的特征值為λi(i=1,2,…,n),不妨設(shè)λ1≥λ2≥…≥λn,則圖G的能量[7]被定義為：

圖G的Estrada指數(shù)[1]被定義為：

基于上述指數(shù)，Zangi等[9]定義了n階連通圖G的ISI矩陣AISI=AISI(G)，其(i,j)元素為

設(shè)ξ1≥ξ2≥…≥ξn為ISI矩陣AISI(G)的特征值，稱ξ1為圖G的ISI譜半徑。圖G的ISI能量[8]定義為：

圖G的ISI-Estrada指數(shù)[10]定義為：

對(duì)于文中部分符號(hào)和術(shù)語，見參考文獻(xiàn)[10-11]。

1 ISI-Estrada指數(shù)的基本性質(zhì)

由ISI-Estrada指數(shù)的定義，可以得到以下結(jié)論：

(1)

由圖的ISI矩陣的定義可知，對(duì)于任意的邊vivj∈E(G)，則它的權(quán)值aij為

(2)

故圖G的第k階ISI譜矩等于圖G的每一個(gè)k長(zhǎng)自回路中邊的權(quán)值的乘積的和，即

(3)

其中，Ct(G)(3≤t≤n)表示圖G中長(zhǎng)為t的圈的集合。

結(jié)論2設(shè)Δ=Δ(G)與δ=δ(G)分別為圖G的最大度與最小度，則

1) 對(duì)于任意的vi∈V(G),有

1≤δ≤di≤Δ≤n-1

2) 對(duì)于任意的vivj∈E(G)，根據(jù)di,dj≥1

di(dj-1)+dj(di-1)≥0

則

(4)

3) 通過基本不等式，對(duì)于任意的vivj∈E(G)，有

(5)

結(jié)論3由于二部圖的ISI矩陣是對(duì)稱的，故其特征值滿足ξn-i+1=-ξi,i=1,2,…,n。因此，若圖G為二部圖，n0為圖G所對(duì)應(yīng)的ISI矩陣的零度，則

(6)

引理1設(shè)G為n個(gè)頂點(diǎn)的簡(jiǎn)單圖，ξi(i=1,2,…,n)為ISI矩陣AISI(G)的特征值，則

(7)

當(dāng)且僅當(dāng)圖G為二部圖時(shí)等號(hào)成立。

引理3完全二部圖Kp,q的ISI矩陣特征值為

2 圖的ISI-Estrada指數(shù)的界

利用ISI-Estrada指數(shù)的基本性質(zhì)，根據(jù)頂點(diǎn)數(shù)和邊數(shù)、零度等圖的不變量給出關(guān)于圖的ISI-Estrada指數(shù)的上下界。

定理1設(shè)G為n個(gè)頂點(diǎn)m條邊的簡(jiǎn)單圖，則

(8)

證明先證上界。由式(1)可知

(9)

即

(10)

再證下界。由ISI-Estrada指數(shù)的定義可以得到

(11)

利用算數(shù)幾何不等式，有

(12)

(13)

其中aij為圖G中的邊γ∈[0,8]的權(quán)值。為了取得更好的下界，設(shè)乘數(shù)γ∈[0,8]，則有

(14)

即

(15)

將式(15)和式(12)代入式(10)可以得到

則

(16)

設(shè)函數(shù)

因?yàn)閒(x)在區(qū)間[0,8]上單調(diào)遞減，故當(dāng)γ=0時(shí)f(x)取得最大值，此時(shí)EEISI取得最優(yōu)下界，即

定理2設(shè)G為n個(gè)頂點(diǎn)、m條邊的簡(jiǎn)單圖，r3為G中圈長(zhǎng)為3的圈的個(gè)數(shù)，則

(17)

證明根據(jù)式(13)，利用第二階、第三階ISI譜矩展開，則

利用與定理1中同樣的方法，設(shè)乘數(shù)γ∈[0,16],則可以得到

定理3設(shè)圖G為n階簡(jiǎn)單圖，k0(≥2)是一個(gè)整數(shù)，則

(18)

證明采用與定理1、定理2同樣的方法，按第k階ISI譜矩展開可以得到上述定理。

當(dāng)k0=2時(shí)，式(18)為定理1的下界，k0=3時(shí)為定理2。

定理4設(shè)圖G是具有n個(gè)頂點(diǎn)、m條邊的簡(jiǎn)單圖，且整數(shù)k≥2，則

(19)

證明由ISI-Estrada指數(shù)的定義有

則

在上述定理中，令k0=2，則有

(20)

此上界優(yōu)于定理1中的上界。

定理5設(shè)圖G為邊數(shù)為m的n階簡(jiǎn)單圖，且ISI矩陣的零度n0

(21)

當(dāng)且僅當(dāng)G是由孤立點(diǎn)和多個(gè)完全二部圖Kr,r(r為常數(shù)) 組成時(shí)等號(hào)成立。

證明由式(4)可以得到

由引理1與引理2,有

(22)

從引理1可以得知，當(dāng)且僅當(dāng)G是二部圖時(shí)式(22)等號(hào)成立。由ISI矩陣的形式可知，二部圖的ISI矩陣是對(duì)稱的，G的所有非零ISI特征值的絕對(duì)值相等，所以圖G是二部圖，包含2個(gè)不同的ISI特征值或3個(gè)不同的ISI特征值，且每個(gè)連通部分都是正則的[13]。結(jié)合引理3可知，G由孤立點(diǎn)和多個(gè)完全二部圖Kr,r(r為常數(shù))組成，證畢。

定理6設(shè)圖G是有n個(gè)頂點(diǎn)、m條邊的二部圖，則

(23)

證明用n+表示圖G的ISI矩陣正特征值的個(gè)數(shù)。由矩陣?yán)碚摰幕拘再|(zhì)，可以得知它與負(fù)ISI特征值的個(gè)數(shù)相等。因此，有n0+2n+=n。由ISI-Estrada指數(shù)的定義和式(5)可知，若

成立，則

3 圖的ISI-Estrada指數(shù)與ISI能量之間的關(guān)系

利用ISI-Estrada指數(shù)的基本性質(zhì)，根據(jù)矩陣的特征值等圖的不變量給出ISI-Estrada指數(shù)與ISI能量之間的關(guān)系。

定理7設(shè)G是有n個(gè)頂點(diǎn)、m條邊的簡(jiǎn)單圖，n+表示圖G的ISI矩陣正特征值的個(gè)數(shù)，則

(24)

證明先證下界。對(duì)于任意x≥0,有ex≥1+x,對(duì)于任意x>0,有ex≥ex,則

e(ξ1+ξ2+…+ξn+)+

(n-n+)+(ξn++1+…+ξn)=

(e-1)(ξ1+ξ2+…+ξn+)+

再證上界。對(duì)于任意x≤0，有ex≤1,根據(jù)ISI-Estrada指數(shù)的定義，則

證畢。

定理8設(shè)G是有n個(gè)頂點(diǎn)、m條邊的簡(jiǎn)單圖，則

(25)

證明根據(jù)ISI-Estrada指數(shù)的定義有

證畢。

定理9設(shè)G是有n個(gè)頂點(diǎn)、m條邊的簡(jiǎn)單圖，則

EEISI(G)≤n-1+eEISI(G)

(26)

證明由ISI-Estrada指數(shù)的定義有

n-1 +eEISI(G)

證畢。

定理10設(shè)G是有n個(gè)頂點(diǎn)、m條邊的簡(jiǎn)單圖，則

(27)

證明設(shè)n+、n0、n-分別為ISI矩陣的正、零、負(fù)特征值的個(gè)數(shù)，ξ1≥ξ2≥…≥ξn+為圖G的ISI矩陣的正特征值，ξn-n-+1,…,ξn為ISI矩陣的負(fù)特征值。由ISI能量的定義有

由算數(shù)幾何平均不等式有

同理，

對(duì)于ISI矩陣的零特征值，有

故

證畢。

4 結(jié)論

1) 利用ISI-Estrada指數(shù)的基本性質(zhì)，考慮ISI-Estrada指數(shù)與圖的頂點(diǎn)數(shù)和邊數(shù)等圖不變量之間的關(guān)系，分別給出了ISI-Estrada指數(shù)的上下界、二部圖的ISI-Estrada指數(shù)的上下界、ISI-Estrada指數(shù)與ISI能量之間的關(guān)系。

2) 僅研究了二部圖這一類特殊圖的ISI-Estrada指數(shù)的界，下一步將研究其他特殊圖的ISI-Estrada指數(shù)的界，進(jìn)一步刻畫更精確ISI-Estrada指數(shù)的界。