懸掛點(diǎn)數(shù)固定的圖的Estrada指標(biāo)

賈會(huì)才，劉付軍

(河南工程學(xué)院 理學(xué)院，河南 鄭州 451191)

?

懸掛點(diǎn)數(shù)固定的圖的Estrada指標(biāo)

賈會(huì)才，劉付軍

(河南工程學(xué)院 理學(xué)院，河南 鄭州 451191)

摘要：圖G的Estrada指標(biāo)定義為e(λi)，其中λ1,λ2,…,λn是圖G的鄰接矩陣的特征值，主要刻畫了懸掛點(diǎn)數(shù)固定的一般圖中具有最大Estrada指標(biāo)的唯一圖.

關(guān)鍵詞：懸掛點(diǎn)數(shù)；鄰接譜；Estrada指標(biāo)

對(duì)具有n個(gè)頂點(diǎn)的圖G1和圖G2,如果Mk(G1)≤Mk(G2)，?k∈z+,則有EE(G1)≤EE(G2),等號(hào)成立當(dāng)且僅當(dāng)?k∈Z+，Mk(G1)=Mk(G2).對(duì)于u,v∈V(G)，定義Wk(G;u,v)為圖G中長(zhǎng)度為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).

對(duì)于圖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)且存在某個(gè)正整數(shù)k，使得Mk0(G1;u1,v1)

Estrada指標(biāo)在很多問(wèn)題中都有重要應(yīng)用,它可以運(yùn)用于確定長(zhǎng)鏈分子，特別是蛋白質(zhì)的可折疊的度[1-2]，在衡量復(fù)雜的網(wǎng)絡(luò)中心時(shí)它也是重要工具.除此之外，Estrada指標(biāo)在數(shù)學(xué)中也有廣泛的應(yīng)用[3-5].Ilic等[6]在最大度固定的樹中刻畫了具有最小Estrada指標(biāo)的唯一樹.Zhang等[7]在匹配數(shù)固定的樹中確定了具有最大Estrada指標(biāo)的唯一樹.Du等[8]確定了單圈圖中具有最大Estrada指標(biāo)的圖.Wang等[9]確定了雙圈圖中具有最大Estrada指標(biāo)的圖.Zhu等[10]確定了三圈圖中具有最大Estrada指標(biāo)的圖.Huang等[11]分別刻畫了匹配數(shù)、點(diǎn)連通度和邊連通度固定的二部圖中Estrada指標(biāo)達(dá)到最大的唯一圖.受上述問(wèn)題的啟發(fā)，考慮懸掛點(diǎn)數(shù)固定的一般圖中Estrada指標(biāo)達(dá)到最大的唯一圖,其他Estrada指標(biāo)更多的數(shù)學(xué)性質(zhì)可以在文獻(xiàn)[12]中找到.

1懸掛點(diǎn)數(shù)為t且具有最大的Estrada 指標(biāo)的唯一圖

引理1[13]設(shè)G是一個(gè)圖，若e?E(G)，則EE(G+e)>EE(G).

引理2[14]設(shè)G是包含點(diǎn)u和v的連通圖，H是含有點(diǎn)ω的非平凡連通圖，如果(G;u,u)>(G;v,v), 那么EE(G(u)·H(ω))>EE(G(v)·H(ω)).

定理3DS(1,n-3)是懸掛點(diǎn)數(shù)為t=n-2的一般圖中具有最大的Estrada指標(biāo)的唯一的圖.

證明若可以證明(G;u,u)>(G;v,v),那么由引理2可知，點(diǎn)v2,…,vn-2-p黏合在點(diǎn)u上得到的圖的Estrada指標(biāo)比黏合在點(diǎn)v上得到的圖的Estrada指標(biāo)大，故結(jié)論得證，所以下面的任務(wù)就是證明(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)是懸掛點(diǎn)數(shù)為t且具有最大的Estrada指標(biāo)的唯一的圖.

證明令圖G*≌是懸掛點(diǎn)數(shù)固定(記為t)的一般圖中Estrada指標(biāo)達(dá)到最大的圖.由引理1可知，圖中n-t個(gè)點(diǎn)必然構(gòu)成一個(gè)團(tuán)Kn-t.又由引理1知，圖G*是連通的，那么剩下的t個(gè)懸掛點(diǎn)都必須與Kn-1的某一點(diǎn)相鄰.先證明(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)

重復(fù)利用這樣的步驟，可以得到在圖G*中，這t個(gè)懸掛點(diǎn)一定都連接在Kn-t的一個(gè)共同頂點(diǎn)上，于是G*=Kn-t(t),定理4得證.

參考文獻(xiàn)：

[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

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-330X(2016)01-0078-03

作者簡(jiǎn)介：賈會(huì)才(1981-),男,河南許昌人,講師,主要從事圖論方面的研究.

基金項(xiàng)目：河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(13B110939)

收稿日期：2015-12-30