, , ,

(College of Mathematics and Statistics,South-Central University for Nationalities,Wuhan 430074,China)

Bicyclic Graphs with Extremal Multiplicative Degree-Kirchhoff Index

ZhuZhongxun,HongYunchao*,LuoAmu,WangWeifeng

(College of Mathematics and Statistics,South-Central University for Nationalities,Wuhan 430074,China)

distance；multiplicativedegree-Kirchhoffindex；bicyclicgraphs

LetG=(V(G),E(G))beaconnectedsimplegraph.ThedistancedG(x,y)isdefinedasthelengthofashortestpathbetweenverticesxandyinG.SupposethatG1andG2aretwodisjointconnectedgraphswithu1∈V(G1)andu2∈V(G2),let(G1,u1)⊕(G2,u2)bethegraphcreatedbycoalescenceofverticesu1andu2.AgraphGiscalledbicyclicgraphif|E(G)|=|V(G)|+1[1,2].

Fig.圖1 圖

Fig.圖2 圖和

The following lemmas that will be used in the proof of our main results.

Lemma 1[4]Letube a cut vertex of a connected graphG,xandybe two vertices in different components ofG-u,thenrG(x,y)=rG(x,u)+rG(u,y).

Lemma 2[7,8]LetPn,CnandSnbe the path,the cycle and the star onnvertices,respectively. Then

R*(Sn)=(n-1)(2n-3).

Lemma 3[7,8]LetG1andG2be connected graphs with disjoint vertex sets,withm1andm2edges,respectively. Letu1∈V(G1) andu2∈V(G2). Constructing the graphGby identifying the verticesu1andu2,and denote the so obtained vertex byu. Then

1 Some Transformations

Inthissection,wewillgivesometransformationswhichwilldecreaseorincreaseR*(G).

Transformation1Letu1u2beacut-edgeofbicyclicgraphG,Cp,CqbetheconnectedcomponentsofG-u1u2,whereu1∈V(Cp),u2∈V(Cq) .

ConstructingthegraphG*fromGbydeletingu1u2andidentifyingtheverticesu1,u2,denotethesoobtainedvertexbyu,addinganpendentedgeuv.

Lemma4LetG,G*bethegraphsdescribedinTransformation1,thenR*(G)>R*(G*).

ProofLet|V(Cp)|=p,|V(Cq)|=q,and|E(Cp)|=p,|E(Cq)|=q.LetH=G[V(G)(V(Cq)-u2)],H*=G[V(G*)(V(Cq)-u)].

ByLemma3,wehave:

Letβnbe the class of connected graphs onnvertices. By Transformation 1 and Lemma 4,we have the following result.

Corollary 1 LetG0be a graph with the smallest multiplicative degree-Kirchhoff index inβn,then all cut-edges are pendent edges.

Transformation 2 LetGbe a bicyclic graph withV(G)={u,v,v1,v2,…,vs}∪V(Cp)∪V(Cq),for whichvis a vertex of degrees+1 such thatvv1,vv2,…,vvsare pendent edges incident withv,anduis the neighbor ofvdistinct fromvithat is on the cycleCq. The other cycleCponly has one common vertexwwithCq. We form a graphG′=σ(G,v) by deleting the edgesvv1,vv2,…,vvsand adding new edgesuv1,uv2,…,uvs. We say thatG′ is aσ-transform of the graphG.

Lemma 5 LetGandG′ be the graphs defined in Transformation 2. ThenR*(G)>R*(G′).

Proof LetT=G[{v,v1,v2,…,vs}],H=G[V(G)V(T)],then

dG(u)dG(v)rG(u,v).

dG′(u)dG′(v)rG′(u,v).

Lemma 6 LetG0be a bicyclic graphGwithV(G)={v1,v2,…,vs}∪V(Cp)∪V(Cq),for whichuis a vertex of degrees+2 in the cycleCqof the bicyclic graphG0,anduv1,uv2,…,uvsare pendent edges incident withu,and the other cycleCponly has one common vertexwwithCq. Let graphG1delete the edgesuv1,uv2,…，uvs,and add new edgeswv1,wv2,…,wvs. ThenR*(G0)>R*(G1).

Proof LetG=G0[V(Cp)∪V(Cq)],H0=G[V(G0)(V(G)-u)],andH1=G[V(G1)(V(G)-w)],thenH0?H1?K1,s. By Lemma 3,we have:

R*(G1)=R*(G)+R*(K1,s)+

Hence we get:

Then we haveR*(G0)>R*(G1).

Transformation 3 LetGbe a bicyclic graph withV(G)={u,v,v1,v2,…,vs}∪V(Cp)∪V(Cq),for whichvis a vertex of degrees+1 such thatvv1,vv2,…,vvsare pendent edges incident withv,anduis the neighbor ofvdistinct fromvithat is on the cycleCq. The other cycleCponly has one common vertexwwithCq. We form a graphG″=π(G,v) by deleting the edgesvv1,vv2,…，vvsand connectingviand all the isolated vertices into a pathvv1v2…vs.

We say thatG″ is aπ-transform of the graphG.

Lemma 7 LetGandG″ be the graphs defined in Transformation 3. ThenR*(G)

Proof LetT=G[{v,v1,v2,…,vs}],H=G[V(G)V(T)],R*(G) is defined in Lemma5,then

dG″(u)dG″(v)rG″(u,v).

Hence we have:

Lemma 8 LetG0be a bicyclic graph with the vertex setV(Cp)∪V(Cq)∪V(Ps+1), in whichV(Cp)∩V(Ps+1)={v} andV(Cq)∩V(Ps+1)={w}. Forwa∈E(Ps+1), andu∈V(Cq), letG1=(G0-{aw})∪{ua},thenR*(G0)>R*(G1).

Proof LetH,H0andH1be the graphs as shown in Fig.3,then we have

G0=(H,vs-1)⊕(H0,a),

G1=(H,vs-1)⊕(H1,w).

By Lemma 3,we have:

R*(G0)=R*(H)+R*(H0)+2(q+1)·

R*(G1)=R*(H)+R*(H1)+2(q+1)·

HenceR*(G0)-R*(G1)=4(p+s-1)[q-rCq(w,u)]≥0. Ifq=rCq(w,u),thenwanducoincidence,G0andG1is isomorphic. SinceG0andG1is not isomorphic,therefore we getR*(G0)-R*(G1)>0. This completes the proof.

Fig.3 Graphs H,H0 and H1圖3 圖H,H0和H1

2 Main results

In this section,we will characterizen-vertex bicyclic graphs with exactly two cycles having the minimum and maximum multiplicative degree-Kirchhoff index.

(1) In Fig.1,Tvi,TujandTwkare all stars with their centers atvi,ujandwkfor eachi,jandk.

Without loss of generality,suppose that treeTviis not a star. LetG1be constructed fromG0by deleting all the edges ofTviand connecting all the isolated vertices tovi. By Lemma 5,we haveR*(G0)>R*(G1),which contradicts the choice ofG0. Hence (1) holds.

(2) The length of the path connects the two cycles inG0is zero.

Suppose that there exist the length of path isk(k≥1) inG0. Assume thatv1=w0,u1=wk. Lete=wiwi+1be an edge of path. LetG2be the graph obtained fromG0by first contractingeand then attaching a pendent edgewiatowi. Assume thatG01andG02are two components ofG0-eandG21andG22are copies ofG01andG02inG2,respectively. See Fig.4.

Fig.4 Graphs G0 and G2圖4 圖G0和G2

By Lemma 4 and Corollary 1,we haveR*(G0)>R*(G2). This contradicts the hypothesis. Hence (2) holds.

(3) In Fig.1,ifp+q≤n,then onlyTv1(Tv1=Tu1) is nontrivial.

Without loss of generality,suppose to the contrary that treeTui(i≠1) is nontrivial. By Lemma 6,we getR*(G0)>R*(G1), which contradicts the choice ofG0. Hence (3) holds .

According to (1)-(3),we get Theorem 1 .

(1) In Fig.1,Tvi,TujandTwkare all paths with their centers atvi,ujandwkfor eachi,jandk.

Without loss of generality,suppose that treeTviis not a path. LetG1be constructed fromG0by deleting all the edges ofTviand connecting all the isolated vertices into a path. By Lemma 7,we haveR*(G1)>R*(G0),which contradicts the choice ofG0. Hence (1) holds.

(2) Assume thatTw0=Tv1andTwm=Tu1,thenTwiis trivial 0≤i≤m).

If not,without loss of generality,suppose that there is nontrivialTwj. By (1),we know thatTwjis a path withwjas its end vertex and assume thatuis the other end vertex. LetG2=G0-wjwj+1+uwj+1(ifj=m,G2=G0-wj-1wj+uwj-1). Assume thatG01andG02are two components ofG0-wjwj+1andG21andG22are two components ofG2-uwj+1. See Fig.5.

In the following,we proveR*(G2)>R*(G0).

LetH0=G02+wjwj+1,H2=G22+uwj+1,rG(wj,u)=s, then by Lemma 3,we get:

Ifs=0,thenG0andG2isisomorphic.SinceG0andG2isnon-isomorphic.ThereforeweobtainR*(G2)>R*(G0).

Thiscontradictsthehypothesis.Hence(2)holds.

(3)InFig.1,ifp+q≤n,thenTviandTujaretrivialforeachiandj.

Fig.5 Graphs G0 and G2 圖5 圖G0和G2

Without loss of generality,suppose to the contrary that treeTvi(i≠1) is nontrivial. By Lemma 8,we getR*(G0)>R*(G1), which contradicts the choice ofG0. Hence (3) holds.

According to (1)-(3),we get Theorem 2.

3 Bicyclic graphs with extremal multiplicative degree-Kirchhoff index

Proof Letu1,u2,wbe three successive vertices lying on theCpof the bicyclic graphG1. The other cycleCqonly has one common vertexwwithCp. Andwv1,wv2,…,wvsare pendent edges incident withw.

Let the graphG2is obtained by deleting the edgesu1u2and adding the edgewu2. ThenR*(G2)<

R*(G1).

LetH1=G[V(G1)(V(Cq)-w)]，H2=G[V(G2)(V(Cq)-w)]，then

ProofLetu1,w,u2bethreesuccessiveverticeslyingontheCpofthebicyclicgraphG3.ThecycleCpandCqarelinkedwithtwoendverticesvandwofPs+1.LetthegraphG4isobtainedbydeletingtheedgewu2andaddingtheedgeu1u2.ThenR*(G4)>R*(G3).

LetH3=G[V(G3)(V(Cp)-w)],H4=

G[V(G4)(V(H3)-w)].Then

Similarly,bydirectcalculation,wehave:

[1]BondyJA,MurtyUSR.Graphtheorywithapplications[M].NewYork:Macmillan,1976: 16-93.

[2] Liu J B,Zhang S Q,Pan X F,et al. Bicyclic graphs with extremal degree resistance distance [EB/OL].(2016-01-03)[2016-12-28].http://www.arXiv:1606.01281v1.com/2016/01/03/bicyclic-graphs-with-extremal-degree-resistance-distance/.

[3] Bonchev D,Balaban A T,Liu X,et al. Molecular cyclicity and centricity of polyclic graphs I cyclicity based on resistance distances or reciprocal distances [J]. Int J Quantum Chem,1994,50: 1-20.

[4] Klein D J,Randic M. Resistance distance [J]. J Math Chem,1993,12: 81-95.

[5] Gutman I,Feng L. Degree resistance distance of unicyclic graphs [J]. Trans Comb 1,2012,1: 27-40.

[6] Chen H Y,Zhang F J. Resistance distance and the normalized Laplacian spectrum [J]. Discr Appl Math,2007,155: 654-661.

[7] Palacios J L,Renom J M. Another look at the degree-Kirchhoff index [J]. Int J Quantum Chem,2011,111:3453-3455.

[8] Palacios J L. Upper and lower bounds for the additive degree-Kirchhoff index [J]. Match Commun Math Comput Chem,2013,70:651-655.

2016-11-17 *通訊作者 洪運朝，研究方向：圖論；E-mail:331963706@qq.com

朱忠熏(1973-),男，副教授，博士，研究方向：圖論；E-mail:zzxun73@mail.scuec.edu.cn

國家自然科學基金資助項目(61070197)；中南民族大學中央高?；究蒲袠I(yè)務費專項資金資助項目(CZQ10007)

O

A

1672-4321(2017)02-0148-07

具有乘積度-基爾霍夫指標極值的雙圈圖

朱忠熏，洪運朝*，羅阿木，王維峰

(中南民族大學 數(shù)學與統(tǒng)計學學院，武漢430074)

距離；乘積度-基爾霍夫指標；雙圈圖