悬挂点数固定的图的Estrada指标

贾会才，刘付军

(河南工程学院 理学院，河南 郑州 451191)



悬挂点数固定的图的Estrada指标

贾会才，刘付军

(河南工程学院 理学院，河南 郑州 451191)

摘要：图G的Estrada指标定义为e(λi)，其中λ1,λ2,…,λn是图G的邻接矩阵的特征值，主要刻画了悬挂点数固定的一般图中具有最大Estrada指标的唯一图.

关键词：悬挂点数；邻接谱；Estrada指标

对具有n个顶点的图G1和图G2,如果Mk(G1)≤Mk(G2)，∀k∈z+,则有EE(G1)≤EE(G2),等号成立当且仅当∀k∈Z+，Mk(G1)=Mk(G2).对于u,v∈V(G)，定义Wk(G;u,v)为图G中长度为k的(u,v)-途径的集合，记Mk(G;u,v)=|Wk(G;u,v)|.为了方便，记Wk(G;u)=Wk(G;u,u),Mk(G;u)=Mk(G;u,u).

对于图G1和图G2，u1,v1∈V(G1),u2,v2∈V(G2)，如果∀k∈Z+，Mk(G1;u1,v1)≤Mk(G2;u2,v2)，写作(G1;u1,v1)≤(G2;u2,v2).如果(G1;u1,v1)≤(G2;u2,v2)且存在某个正整数k，使得Mk0(G1;u1,v1)

Estrada指标在很多问题中都有重要应用,它可以运用于确定长链分子，特别是蛋白质的可折叠的度[1-2]，在衡量复杂的网络中心时它也是重要工具.除此之外，Estrada指标在数学中也有广泛的应用[3-5].Ilic等[6]在最大度固定的树中刻画了具有最小Estrada指标的唯一树.Zhang等[7]在匹配数固定的树中确定了具有最大Estrada指标的唯一树.Du等[8]确定了单圈图中具有最大Estrada指标的图.Wang等[9]确定了双圈图中具有最大Estrada指标的图.Zhu等[10]确定了三圈图中具有最大Estrada指标的图.Huang等[11]分别刻画了匹配数、点连通度和边连通度固定的二部图中Estrada指标达到最大的唯一图.受上述问题的启发，考虑悬挂点数固定的一般图中Estrada指标达到最大的唯一图,其他Estrada指标更多的数学性质可以在文献[12]中找到.

1悬挂点数为t且具有最大的Estrada 指标的唯一图

引理1[13]设G是一个图，若e∉E(G)，则EE(G+e)>EE(G).

引理2[14]设G是包含点u和v的连通图，H是含有点ω的非平凡连通图，如果(G;u,u)>(G;v,v), 那么EE(G(u)·H(ω))>EE(G(v)·H(ω)).

定理3DS(1,n-3)是悬挂点数为t=n-2的一般图中具有最大的Estrada指标的唯一的图.

证明若可以证明(G;u,u)>(G;v,v),那么由引理2可知，点v2,…,vn-2-p黏合在点u上得到的图的Estrada指标比黏合在点v上得到的图的Estrada指标大，故结论得证，所以下面的任务就是证明(G;u,u)>(G;v,v).

任取W=vuusu…uvv1v∈(G;v,v),其中s=1,2,…,p，若

(1)v1∉W，则存在映射Φ，有Φ(vuusu…uv)=uusu…uvu，即Φ(W)∈(G;u,u)；

(2)v1,u∈W，则存在映射Φ，有Φ(vuusu…uvv1v)=uusu…uvv1vu，即Φ(W)∈(G;u,u)；

(3)u∉W，则存在映射Φ，有Φ(vv1…vv1v)=uu1…uu1u，即Φ(W)∈(G;u,u)；

综上所述，(G;u,u)>(G;v,v).

定理4Kn-t(t)是悬挂点数为t且具有最大的Estrada指标的唯一的图.

证明令图G*≌是悬挂点数固定(记为t)的一般图中Estrada指标达到最大的图.由引理1可知，图中n-t个点必然构成一个团Kn-t.又由引理1知，图G*是连通的，那么剩下的t个悬挂点都必须与Kn-1的某一点相邻.先证明(G;v1,v1)>(G;vk,vk),k=2,3,…,n-t.

任取W=vkvsvt…vpvqvk∈(G;vk,vk),若

(1)u1∉W，则存在映射Φ，使Φ(vk)=v1，Φ(v1)=vk,Φ(vl)=vl,l≠1,K,即Φ(W)∈(G;v1,v1)；

(2)u1∈W，则存在映射Φ，有Φ(vkvsvt…v1u1v1…vpvqvk)=v1vkvsvt…v1u1v1…vpv1，即Φ(W)∈(G;v1,v1)；

综上所述，(G;vk,vk)≤(G;v1,v1).

又由M2(G;vk)=n-t-1

由引理2可知，EE(G2)

重复利用这样的步骤，可以得到在图G*中，这t个悬挂点一定都连接在Kn-t的一个共同顶点上，于是G*=Kn-t(t),定理4得证.

参考文献：

[1]ESTRADA E.Characterization of the folding degree of proteins[J].Bioinformatics,2002(18):697-704.

[2]ESTRADA E.Characterization of the amino acid contribution to the folding degree of proteins[J].Proteins,2004(54):727-737.

[3]LI J,LI X,WANG L.The minimal Estrada index of trees with two maximum degree vertices[J].Match Communications in Mathematical and in Computer Chemistry,2010(64):799-810.

[4]ZHOU B.On Estrada index[J].Match Communication in Mathematical and in Computer Chemistry,2008(60):485-492.

[5]ZHOU B,TRINAJSTIC N.Estrada index of bipartite graphs[J].International Journal of Chemical Modeling,2008(1):387-394.

[6]ILIC A,STERANOVIC D.The Estrada index of chemical trees[J].Journal of Mathematical Chemistry,2010(47):305-314.

[7]ZHANG J,ZHOU B,LI J.On Estrada index of trees[J].Linear Algebra and Its Applications,2011(434):215-223.

[8]DU Z,ZHOU B.The Estrada index of unicyclic graphs[J].Linear Algebra and Its Applications,2012(436):3149-3157.

[9]WANG L,FAN Y Z,WANG Y.Maximun Estrada index of bicyclic graphs[J].Discrete Applied Mathematics,2014(180):194-199.

[10]ZHU Z X,TAN L S,QIU Z Y.Tricyclic graph with maximun Estrada index[J].Discrete Applied Mathematics,2014(162):364-372.

[11]HUANG F,LI X L,WANG S J.On maximun Estrada indices of bipartite graphs with some given parameters[J].Linear Algebra anh Its Applications,2015(465):283-295.

[12]GUTMAN I,DENG H,RADERKOVIC S.The Estrada index:an updated survey,in:Cretkovic D,Gutman I(Eds),selected topics on applications of graph spectra[J].Mathematisches Institute Beograd,2011(1):155-174.

[13]GUTMAN I,ESTRADA E,RODRIGUEZ V J A.On a graph-spectrum-based structure descripter[J].Croatica Chemica Acta,2007(80):151-154.

[14]DU Z,ZHOU B,XING R.On maximun Estrada indices of graphs with given parameters[J].Linear Algebra and Its Applications,2012(436):3767-3772.

The Estrada indices of graphs with given number of pendent vertices

JIA Huicai, LIU Fujun

(CollegeofSciences,HenanUniversityofEngineering,Zhengzhou451191,China)

Abstract:The Estrada index of a graph G is defined as e(λi) , where λ1,λ2,…,λn are the eigenvalues of the adjacency matrix of G.In this paper, we characterize the unique graph with maximum Estrada index among all graphs with given number of pendent vertices.

Key words:number of pendant vertices; adjacency spectrum; Estrada index

中图分类号：O157.5

文献标志码：A

文章编号：1674-330X(2016)01-0078-03

作者简介：贾会才(1981-),男,河南许昌人,讲师,主要从事图论方面的研究.

基金项目：河南省教育厅科学技术研究重点项目(13B110939)

收稿日期：2015-12-30