Estrada指數(shù)的極小樹

王 杰，朱業(yè)春，杜文學(xué)

（1.中國科學(xué)技術(shù)大學(xué) 安徽 合肥230009；2.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥230601）

1 引 言

設(shè)G是一個具有n個頂點(diǎn)的簡單圖，G的鄰接矩陣為n×n階的矩陣A(G)=(aij)n×n其中

顯然A(G)是一個對稱的(0,1)-矩陣。由于A(G)是實對稱的，故它的n個特征值均為實數(shù)。不妨記作:λ1，λ2，…，λn。

圖G的k階譜矩Mk(G)定義為：Mk(G)=Mk(A(G))。Cvetkovi 等人[1]指出k階譜矩的值等于長度為k的閉道的個數(shù)。2000年Estrada 在文獻(xiàn)[2]中引入了一個度量高分子長鏈的折疊度的指標(biāo)，這個指標(biāo)后來被稱為圖的Estrada 指數(shù)。定義為:EE(G)。通過將ex冪級數(shù)展開易知:

圖的Estrada 指數(shù)是近年來興起的研究熱點(diǎn)，自從Estrada 指數(shù)被提出來以后，它已經(jīng)被廣泛地應(yīng)用于分子化學(xué)，量子化學(xué)，信息科學(xué)，復(fù)雜網(wǎng)絡(luò)等領(lǐng)域。比如它被用來定量描述折疊的長鏈聚合物分子的度，尤其是蛋白質(zhì)分子。[3]之后有學(xué)者研究了Estrada 指數(shù)與廣義的原子軌道的聯(lián)系。[4]在復(fù)雜網(wǎng)絡(luò) 領(lǐng) 域，Estrada 和Rodríguez-Velázquez 證 明 了Estrada 指數(shù)能夠用來反應(yīng)網(wǎng)絡(luò)的集中性。[5，6]

Deng，[7]Das 和Lee[8]等人已經(jīng)證實：對任何n個頂點(diǎn)的樹T，有EE（Sn）≥EE（T）≥EE（Pn），這里Sn，Pn分別表示n個頂點(diǎn)的星圖和路，而且EE（Sn）≥EE（T）當(dāng)且僅當(dāng)T?Sn，EE（T）=EE（Pn）當(dāng)且僅當(dāng)T?Pn。由此我們知道，星圖Sn是唯一的擁有最大的Estrada 指數(shù)的n個頂點(diǎn)的樹，Pn是唯一的擁有最小的Estrada 指數(shù)的n個頂點(diǎn)的樹。更進(jìn)一步地，和Stevan-ovi在擁有一個最大度的樹中確定了唯一的擁有最小Estrada 指數(shù)的樹。[9]張等人在給定匹配數(shù)目的樹中確定了唯一的擁有最大Estrada 指數(shù)的樹。[10]

由于各位學(xué)者在證明各圖類的Estrada 指數(shù)極圖的過程中，只是在圖類比較小的特定范圍內(nèi)來討論, 例如上述的和Stevanoviá?為了擴(kuò)大圖類的特定范圍，使得結(jié)論更具有普遍的意義，在本文中，將確定擁有兩個最大度的樹的Estrada 指數(shù)的極小圖，并給出擁有任意個k最大度的樹(記T(n,△,k))的Estrada 指數(shù)極小圖的猜想。

2 T(n，△，2)的Estrada 指數(shù)極小圖

設(shè)有樹圖T(n，△，2)，其最大度點(diǎn)集合V△={v∈V(T):dT (v)=△}，|V△|=2，v1，v2為最大度點(diǎn)，如圖1 所示。對T(n，△，2)進(jìn)行指定操作后得到T'，使其滿足T'→T有的單射，從而EE(T')≤EE(T)。不斷地進(jìn)行此類操作，直至不能再得到滿足條件的T' 為止，我們就得到了T(n，△，2)的Estrada 指數(shù)極小圖。

圖1

引理1：設(shè)S（n，k）為擁有最大度為k(k≤n-1)的n個頂點(diǎn)樹，如圖2 所示。易知存在W2k(v3)→W2k(v2)的映射ξ1，使得ξ1是單射而非滿射，其中W2k(v3)和W2k(v2)是分別以v3和v2為始終點(diǎn)，長為2k的閉道的集合。

圖2

證明: 設(shè)ξ1:W2k(v3)→W2k(v2)。我們可知對任意w∈W2k(v3):w=v3v2v1…vi2k-3v2v3，定有ξ1（w）=v2v3v2vi1…v2k-3v2。同時我們易知ξ1是單射，因為dT(v2)≥2，因此沒有w∈W2k(v3)，使得ξ1（w）不經(jīng)過邊v2v3。綜上：ξ1是單射而非滿射。

定理1：圖3 所示的雙星圖是T (n,△，2)的Estrada 指數(shù)極小圖。

圖3

證明第1 步：將T(n,△，2)最大度點(diǎn)上的各個分支進(jìn)行手術(shù)，轉(zhuǎn)化為路徑。易知此步驟均會使EE（T）不斷地減小，此操作后如圖4 所示。

圖4

第2 步：將圖4 進(jìn)行如圖5 的操作，去掉邊v3，v4，將v5連接v4，我們要證明此操作后會使EE（T）減小。

圖5

證明：對修改后的圖中含v4的閉道W'(v4)進(jìn)行分類討論，尋找T'→T的單射。

1.若閉道中不含有v4，則顯然此閉道也在T中。

2.W'(v4)∩{v5}=?，則W'(v4)?T。

3.W'(v4)∩{v5}≠?，W'(v4)∩{v2}=?。

5.W'(v4)∩{v3}≠?。

據(jù)此，所定義的操作會將EE變小，即EE(T')≤EE(T)。

第3 步：將第2 步得到的樹再進(jìn)行如圖6 的操作，將邊v3v4去掉，把v4連接到v5上。同樣我們要證明EE(T)是減小的。

圖6

證明：對修改后的圖中含v4的閉道W'(v4)分類討論，尋找T'→T的單射。

1.若閉道中不含有v4，則顯然此閉道也在T中。

2.W'(v4)∩{v5}=?，W'(v4)∩{v1}=?。

3.W'(v4)∩{v1}≠?，W'(v4)∩{v3}=?。

4.W'(v4)∩{v3}≠?。

據(jù)此，所定義的操作會EE將變小，即EE(T')≤EE(T)。

第4 步：經(jīng)第3 步的不斷修改，得到如圖7 的樹，我們再進(jìn)行手術(shù)，將邊v3v4去掉，把v4連接到v5上。同樣我們要證明EE(T)是減小的。

圖7

證明：對修改后的圖中含v5的閉道W'(v5)分類討論，尋找T'→T

1.若閉道中不含有v5，則顯然此閉道也在T中。

2.W'(v5)∩{v4}=?，則W'(v5)?T。

3.W'(v5)∩{v4}=?，則將v5→v3。

據(jù)此，所定義的操作會將EE變小，即EE(T')≤EE(T)。

綜上，運(yùn)用這4 個步驟，就可以找到T(n，△，2)的極小圖(即雙星圖)。

3 T(n，△，k)的Estrada 指數(shù)極小圖

設(shè)有樹圖T (n，△，k)，其最大度點(diǎn)集合V△={v∈V（T）:dT（v）=△}，|V△|=k，v1，v2，…，vk為最大度點(diǎn)。對T(n，△，k)進(jìn)行相關(guān)操作后，使得最后修改后的樹圖中，最長的路徑為n-k△+2k，且最大度點(diǎn)在最長的路徑上分布最均勻(即任意兩個最大度點(diǎn)之間都含有個點(diǎn))，即如圖8 所示，我們把其命為多星圖。

圖8

猜想：多星圖是T(n，△，k)的Estrada 指數(shù)極小圖。

[2]E.Estrada.Characterization of 3D molecular structure [J].Chem Phys Lett，2000，319：713-718.

[3]E.Estrada.Characterization of the folding degree of proteins[J].Bioinformatics，2002，18：697-704.

[4]E.Estrada.Characterization of the amino acid contribution to the folding degree of p-roteins[J].Proteins，2004，54：727-737.

[5]E.Estrada.J.A.Rodríguez‐Valázquez.Spectral measures of bipartivity in complex networks [J].Phys.Rev，2005，E,72：0461051-0461056.

[6]E.Estrada.J.A.Rodríguez‐Valázquez.Subgraph centrality in complex networks [J].Phys Rev E，2005，72：0561031-0561039.

[7]H.Deng.A proof of a conjectures on the Estrada index [J].Match，2009，62：607-610.

[8]K.Das.S.Lee.On the Estrada index conjecture[J].Linear Algebra Appl，2009，431：1351-1359.

[9]A.IliC'.D.Stevanovi.The Estrada index of chemical trees[J].J.Math.Chem，2010，47：305-314.

[10]J.Zhang.B.Zhou.J.Li.On Estrada index of trees [J].Linear Algebra Appl，2011，434：215-223.