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.