楊迎迎, 常 安

(福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,福建 福州 350116)

0 引言

本研究所討論的圖均為簡單圖. 設(shè)G是一個n階圖,其頂點集為V(G)={v1,v2, …,vn}. 圖G的鄰接矩陣是一個n階(0, 1)-矩陣,記為A(G)=(aij). 其中,如果頂點vi和vj相鄰,那么aij=1,否則aij=0.G的特征多項式為P(G,λ)=det[λI-A(G)],其中I是n階單位矩陣.P(G,λ)=0的根即為圖G的特征值,記為(λ1(G),λ2(G), …,λn(G)).

1 預(yù)備知識

設(shè)G、 H是兩個點不交的連通圖,v1、 v2分別是圖G、 H的兩個頂點,將v1和v2粘合在一起形成一個新點u,稱這一過程為圖的粘合[7], 所得的圖記為G(v1)°H(v2)或者H(v2)°G(v1). 下面是證明本研究主要結(jié)論所需要的幾個引理.

引理1[4]設(shè)G和H是兩個點不交的連通圖,u, v∈V(G),z∈V(H),并且 |V(H)|≥2. 記G1=G(u)°H(z),G2=G(v)°H(z). 如果對任何正整數(shù)k都有Mk(G; u, u)≥Mk(G; v, v),并且至少有一個k0滿足Mk0(G; u, u)>Mk0(G; v, v),則EE(G1)>EE(G2).

(a) G′ (b) G″圖1 引理2中的圖G′和G″Fig.1 G′ and G″ in Lemma 2

(a) G1 (b) G2 (c) G3圖2 引理3中的G1,G2和G3Fig.2 G1, G2 and G3in Lemma 3

引理2[4]設(shè)G1和G2是兩個連通圖,且u∈V(G1),v∈V(G2). 圖G′表示將點u和點v用一條邊連接得到的圖,圖G″表示將點u和點v粘在一起,并且在這個公共點u(v)上增加一條懸掛邊得到的圖,如圖1所示. 如果dG1(u)≥2,dG2(v)≥2,則EE(G″)>EE(G′).

引理3[1]設(shè)G、G′、G″是三個點不交的連通圖,u,v∈V(G),u′∈V(G′),u″∈V(G″). 圖G1、G2、G3是由圖G、G′、G″構(gòu)造出來的圖. 其中,G1是分別將點u和點u′,點v和點u″粘在一起得到的圖； 圖G2是將u、u′、u″三點粘在一起得到的圖； 圖G3是將v、u′、u″三點粘在一起得到的圖,如圖2所示. 則EE(G2)>EE(G1)或EE(G3)>EE(G1).更進一步,如果dG(u)≥dG(v),有EE(G2)>EE(G1)； 如果dG(v)≥dG(u),有EE(G3)>EE(G1).

設(shè)Cn表示n個頂點的圈.Cn上的頂點按順時針順序標為u1,u2, …,un.

引理4[1]設(shè)G是一個連通圖,并且Cl是圖G上圈長為l≥5的圈. 如果在Cl上存在一個度數(shù)為2的點(設(shè)為ul),并且點ul-2與點u1不相鄰,則存在另外一個圖G′=G-u1ul+u1ul-2,圖G′中有一個圈長為l-2的圈,并且EE(G′)>EE(G).

引理5[7]設(shè)圖G中有兩個頂點u,v,設(shè)wi∈V(G),uwi?E(G),vwi?E(G)(i=1, 2, …,k). 定義Eu={uwi,i=1, 2, …,k},Ev={vwi,i=1, 2, …,k}.Gu=G+Eu,Gv=G+Ev. 如果(G;u,u)<(G;v,v)并且(G;u,wi)≤(G;v,wi)(i=1, 2, …,k),則有EE(Gu)

2 主要內(nèi)容

證明 首先證明在圖G中,對任意正整數(shù)k,都有Mk(G;u,u)≥Mk(G;v,v). 顯然M1(G;u,u)=0,M1(G;v,v)=0；M2(G;u,u)≥2,M2(G;v,v)=2；M3(G;u,u)≥0,M3(G;v,v)=0. 當(dāng)k≥4時,對于?wk(G;v,v)∈Wk(G;v,v),分兩種情況考慮.

圖3 從G到H的轉(zhuǎn)換Fig.3 The transformation from G to H

(a) 形式1 (b) 形式2圖圖類中的兩種形式

證明 下面分兩種情況討論.

圖5 引理7中圖的轉(zhuǎn)換Fig.5 The transformation of graph in lemma 7

圖

由引理6～7的結(jié)論,即可得到下面主要結(jié)果.

[1]BAMDADH,ASHRAFF,GUTMANI.LowerboundsforEstradaindexandLaplacianEstradaindex[J].AppliedMathematicsLetters, 2010, 23(7): 739-742.

[2]FATH-TABARGH,ASHARFIAR.NewupperboundsforEstradaindexofbipartitegraphs[J].LinearAlgebraandItsApplications, 2011, 435(10): 2607-2611.

[3]DUZB,ZHOUB.TheEstradaindexofunicyclicgraphs[J].LinearAlgebraanditsApplications, 2012, 436(9): 3149-3159.

[4]WANGL,FANYZ,WANGY.MaximumEstradaindexofbicyclicgraphs[J].DiscreteAppliedMathematics, 2015, 180(10): 194-199.

[5] 滕海濱. 單圈圖的匹配與Estrada指標[D]. 合肥： 安徽大學(xué),2013： 1-30.

[6]CVETKOVICDM,DOOBM,SACHSH.Spectraofgraphstheoryandapplication[M].NewYork:AcademicPress, 1980.

[7]WANGWH,XUWW.GraphswiththemaximalEstradaindices[J].LinearAlgebraanditsApplications, 2014, 446(1): 314-328.