Estrada指數的極小樹

王 杰，朱業春，杜文學

（1.中國科學技術大學 安徽 合肥230009；2.安徽大學 數學科學學院，安徽 合肥230601）

1 引 言

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

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

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

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

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

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

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

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

圖1

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

圖2

證明: 設ξ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）不經過邊v2v3。綜上：ξ1是單射而非滿射。

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

圖3

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

圖4

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

圖5

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

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

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

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

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

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

第3 步：將第2 步得到的樹再進行如圖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}≠?。

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

第4 步：經第3 步的不斷修改，得到如圖7 的樹，我們再進行手術，將邊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。

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

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

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

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

圖8

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

[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.