CUI Qingqing,ZHAO Biao

(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)

Abstract: We consider a multiplicative version of Lanzhou index. By introducing some graph transformations that strictly increase or decrease this index, and we characterize the extremal graphs with respect to the multiplicative Lanzhou index over the following sets: trees,unicyclic and bicyclic graphs.

Key words: multiplicative Lanzhou index;tree;unicyclic graphs;bicyclic graphs

0 Introduction

In this paper,we consider only simple,finite and undirected graphs. LetGbe a simple connected graph with vertex setV(G)and edge setE(G). The degree of a vertexv∈V(G)is equal to the number of its neighbors and we denote it bydG(υ). A vertex of degree 1 is called a leaf. We denote by ?(G)and δ(G)the maximum and minimum degrees of the vertices ofG. For anyu∈V(G),the neighborhood ofu,writtenNG(u),is the set of vertices adjacent tou. The complement graphofGhas the same vertex setV(G),and two vertices are adjacent inif and only if they are not adjacent inG. The complete graph,the path and the star onnvertices are denoted byKn,PnandSn. LetG=(V,E)be a connected graph,ifW?V(G),we denote byG-Wthe subgraph ofGobtained by deleting the vertices ofWand the edges associated with them. IfE′?E(G),we denote byG-E′the subgraph ofGobtained by deleting the edges ofE′. IfW={v}andE′={xy},the subgraphsG-WandG-E′will be written asG-vandG-xyfor short. LetG+uvdenote the graph obtained fromGby adding the edgeuv?E(G). For other undefined notations and terminologies from graph theory,the readers are referred to[1].

The first Zagreb indexM1(G)of a graphGis defined as

while the forgotten index ofGis defined as

They were defined in reference[2]. The mathematical and chemical properties of the first Zagreb index have been studied in[3–6]. The forgotten index was reintroduced by Furtula and Gutman in[7].

As is well known, finding extremal graphs and values of the topological indices over some classes of graphs attracts the attention of many researchers. In [8], extremal graphs withnvertices are illustrated. More precisely, complete and empty graphs are of minimum Lanzhou index 0,and 2(n-1)/3-regular graphs withn≡1(mod 3)are of maximum Lanzhou index 4n(n-1)3/27. For trees withnvertices,stars and balanced double stars are the minimal and maximal graphs respectively.

Recently,many scholars have paid great attention to Lanzhou index.

Definition 1[8]For any treeTof ordern≥15,then

with equality if and only ifT=Sn.

Definition 2[8]For any treeTof ordernwith maximum degree at most 4,then

with equality if and only ifT=Pn.

Definition 3[9]For any treeTof ordern≥11 with maximum degree ?. Then

with equality if and only ifTis a spider with the center of degree ?. The tree with only one core is a spider.

Liu et al.[10]proved the extreme value and the extremal graph of the Lanzhou index of the unicyclic graph.

Todeschini et al.[11-12]proposed the multiplicative variants of ordinary Zagreb indices,which are defined as follows

Found by experimental comparison, the multiplicative version of the perturbation delta value and the multiplicative version of the perturbation delta value where the valence vertex degree was replaced by the intrinsic state showed high predictive ability in modeling physico-chemical properties ofC8(namely the hydrocarbons with eight carbon atoms) data set[12]. Mathematical properties and applications of multiplicative Zagreb indices are reported in [11-16]. These two graph invariants are called multiplicative Zagreb indices by Gutman[14]. The bounds of a molecular topological descriptor are important information for a molecular graph in the sense that they establish the approximate range of the descriptor in terms of molecular structural parameters.

Yousefi et al.[17]consider a multiplicative version of forgotten index. The main purpose is to begin to study the mathematical properties of multiplicative forgotten index,in which the upper bounds of several graph operations are proved.

Liu[18]put forward the multiplicative Sombor index, mainly studied the mathematical properties of the multiplicative Sombor index,and extremal values of the multiplicative Sombor index of trees and unicyclic graphs are determined.

Hence,according to the definition of the Lanzhou index,it is natural to consider the multiplicative version of the Lanzhou index,defined as

The aim of this paper is to begin the research on mathematical properties of the multiplicative Lanzhou index. Although this is a definition put forward from a mathematical point of view, it has not been accompanied by at least one chemical application or some physical or chemical properties, but we hope it can be used as a reference that cast a brick to attract a jade.

In papers [16, 19], the authors obtained the extreme values of the multiplicative Zagreb index and the multiplicative sum Zagreb index on trees, unicyclic and bicyclic graphs. This motivates us to find the extreme values of some graphs on the multiplicative Lanzhou topological index. Therefore, in this paper, we mainly introduce some graph transformations to determine the corresponding extreme values and extreme graphs of multiplicative Lanzhou index inT(n),U(n) andB(n).(T(n),U(n)andB(n)are the set of trees of ordern,the set of connected unicyclic graphs of ordernand the set of connected bicyclic graphs of ordern).

1 The Minimum Multiplicative Lanzhou Index of Trees,Unicyclic and Bicyclic Graphs

According to the definition of multiplicative Lanzhou index,we can know that ΠLz(G)=0 if and only if ?(G)=n-1,for any connected graph of ordern. Hence,we discuss the minimum value of multiplicative Lanzhou index when ΠLz(G)≠0 i.e. ?(G)≤n-2.

Theorem 1LetGbe a graph with minimum multiplicative Lanzhou index, in the class of all connected graphs of ordern≥4 with ?(G)≤n-2. Then ?(G)=n-2.

ProofLetube a maximum degree vertex ofG.Suppose thatdG(u)

LetdG(u)=x,dG(wk)=y, thenx≥yanddG′(u)=x+1,dG′(wk)=y-1. Moreover, for every vertex inV(G){u,wk}={t1,t2,···,tn-2},it is easy to see thatdG(ti)=dG′(ti)=dti(i=1,2,···,n-2). Now we calculate the difference between ΠLz(G)and ΠLz(G′).

Because that

then ΠLz(G)>ΠLz(G′).

This contradicts with thatGis a graph with minimum multiplicative Lanzhou index. Hence,?(G)=n-2.

According to Theorem 1,we can get the following results.

LetSn-1,1be a graph as shown in Fig 1, which is obtained by subdividing a pendent edge of starSn-1, then|V(Sn-1,1)|=nand ?(Sn-1,1)=n-2.

Fig 1 The graph of Sn-1,1

Corollary 1LetTbe a tree of ordern≥4 with?(T)≤n-2. Then

with equality if and only ifT?Sn-1,1.

A unicyclic graph of ordernwith ?=n-2 is one of the three graphs shown in Fig 2.

Fig 2 The graph in U(n)with ?=n-2

Transformation BLetGbe a connected graph,uv∈E(G)withdG(u)≥2,dG(v)≥2,andNG(u)∩NG(v)=?. Further,we construct a graphG′which is obtained by identifying the verticesuandvto a vertexu′and attaching a leaf vertexv′to the vertexu′. HenceV(G)=V(G′)=n,letdG(u)=x,dG(v)=y,thendG′(v′)=1,dG′(u′)=x+y-1. Lethi(i=1,2,···,n-2)be a vertex different from{u,v}and{u′,v′}inV(G)=V(G′),thendG(hi)=dG′(hi)=dhi(i=1,2,···,n-2). See Fig 3.

Fig 3 Transformation B

Lemma 1LetGandG′be two graphs as shown in Fig 3. Then ΠLz(G)>ΠLz(G′).

Proof

Because of

Therefore,x2(n-1-x)y2(n-1-y)-(x+y-1)2(n-x-y)12(n-2)>0.

This completes the proof of Lemma 1.

Corollary 2LetUbe a unicyclic graph of ordernwith ?(U)≤n-2. Then

with equality if and only ifU?C3(Sn-3,P2).

ProofLetUbe a unicyclic graph with the minimum multiplicative Lanzhou index. By Theorem 1, we know that?(U)=n-2. Hence

The degree sequences of graphC3(Tn-2)and graphC4(Sn-3)are the same. Therefore

By Transformation B and Lemma 1,we have

Therefore,the graphC3(Sn-3,P2)fromU(n)has minimum multiplicative Lanzhou index,and

Thus we complete the proof of the Corollary 2.

Any graphG∈B(n)possesses at least two cycles, the structure of cycles inGcan be divided into the following three types[20].

(I)The two cyclesCpandCqinGhave only one common vertex υ;

(II)The two cyclesCpandCqinGare linked by a path of lengthl≥1;

(III)The two cyclesCl+kandCl+minGhave a common path of lengthl≥1.

The graphsB1(p,q),B2(p,l,q)andB3(k,l,m)(where 1 ≤l≤min{k,m})corresponding to the types above shown in Fig 4 are called main subgraphs ofG∈B(n)of types(I)～(III),respectively.

Fig 4 The graphs B1(p,q),B2(p,l,q),B3(k,l,m)

Whenn=4,B(n)contains only graph,which is obtained by deleting an edge of complete graphK4,and ΠLz(K4-e)=0.

Whenn=5 and ?=n-2,there are three graphs inB(n). It is easy to calculate the maximum and minimum values of the multiplicative Lanzhou index over these three graphs,shown in Fig 5.

Fig 5 The bicyclic graphs with n=5 and ?=n-2

Whenn≥6, letG∈B(n). IfGis of type(II),then ?(G)≤n-3. IfGis of type(I),there are three bicyclic graphs with?(G)=n-2,shown in Fig 6. IfGis of type(III),there are six bicyclic graphs with ?(G)=n-2,shown in Fig 7.

Fig 6 The bicyclic graphs of type(I)with ?=n-2

Fig 7 The bicyclic graphs of type(III)with ?=n-2

Corollary 3LetBbe a bicyclic graph of ordern≥6 with ?(B)≤n-2. Then

with equality if and only ifB?B3(Sn-4,P2).

ProofLetBbe the bicyclic graph with the minimum multiplicative Lanzhou index. By Theorem 1, we know that?(B)=n-2.

IfBis of type(I),thenB∈{B1(Sn-5,P2),B1(Sn-5),B1(Tn-4)}. The degree sequences of graphB1(Sn-5)and graphB1(Tn-4)are the same,so

By Transformation B and Lemma 1,we have

Hence,the graphB1(Sn-5,P2)from type(I)has minimum multiplicative Lanzhou index. And

IfBis of type(III),thenThe degree sequences of graphsB3(Tn-3),B3(Sn-4)and graphare the same,therefore

By Transformation B and Lemma 1,we have

The degree sequences of graphand graphB3(Sn-3)are the same,hence,

By calculation,

Hence,the graphB3(Sn-4,P2)from type(III)has minimum multiplicative Lanzhou index,and

Since

Hence we conclude that the graphB3(Sn-4,P2)fromB(n)has minimum multiplicative Lanzhou index.

Thus we complete the proof of the Corollary 3.

2 The Maximum Multiplicative Lanzhou Index of Trees,Unicyclic and Bicyclic Graphs

At first,we introduce a graph transformation to increase the multiplicative Lanzhou index of graphs.

Transformation ASuppose thatG0is a nontrivial connected graph and υ is a given vertex inG0. LetG1be a graph obtained fromG0by attaching at υ two pathsP:υu1u2···ukof lengthk≥1 andQ:υw1w2···wkof lengthl≥1. LetG2=G1-υw1+ukw1. HenceAssume thatLethi(i=1,2,···,n-2)be these vertices different from υ andukinV(G1)=V(G2),thenLet ?idenote the maximum degree inGi,then ?i

Fig 8 Transformation A

Lemma 2LetG1andG2be two graphs shown in Fig 8. Then ΠLz(G2)>ΠLz(G1).

Proof

Because from what has been describe abovex>2 andn≥4.

Whenn≥5,we have that

Then,(x-1)2(n-x)22(n-3)-x2(n-1-x)12(n-2)>0.

Whenn=4,it follows thatx=3. Then(2x-2)2(n-x)(n-3)-x2(n-1-x)(n-2)=36>0. Hence ΠLz(G2)>ΠLz(G1).

Thus we complete the proof of the Lemma 2.

LetG,Hbe two nontrivial connected graphs withu∈V(G),v∈V(G), andV(G)∩V(H) = ?. LetG{u,v}Hbe the graph obtained fromGandHby identifyinguwithv.

Theorem 2LetGbe a nontrivial connected graph withu∈V(G),Tmbe a tree of orderm≥2 withv∈V(Tm), andV(G)∩V(Tm)=?. Then ΠLz(G{u,v}Tm)≤ΠLz(G{u,v}Pm), with the equality if and only ifPmis path of ordermandvis an end point ofPm.

ProofSuppose that there is a treeof ordermsuch thatis maximum for all trees of orderm.

By Theorem 2,we can obtain following results.

Corollary 4LetTbe a tree of ordern≥4. Then ΠLz(T)≤ΠLz(Pn),with equality if and only ifT?Pn.

Transformation CLetGbe a nontrivial connected graph,vbe a vertex ofG. A pendent pathP=vu1u2···ut-1utis attached to the vertexvofGand there is a neighborwofvdifferent fromu1. LetG′=G-vw+wuk,thenV(G)=V(G′)=n.LetdG(v)=x(x>2),dG(uk)=1,thendG′(v)=x-1,dG′(uk)=2. Lethi(i=1,2,···,n-2)be these vertices different fromvandukinV(G)=V(G′),andsee Fig 9.

Fig 9 Transformation C

Lemma 3LetGandG′be two graphs shown in Fig 9. Then ΠLz(G′)>ΠLz(G).

Proof

Because of

Therefore,(x-1)2(n-x)22(n-3)-x2(n-1-x)12(n-2)>0.

Thus we complete the proof of the Lemma 3.

Remark 1Applying Theorem 2 and Transformation C, we know that the graph from unicyclic and bicyclic graphs with the maximum multiplicative Lanzhou index must be no pendent edge.

Corollary 5LetUbe a unicylic graph of ordern≥3. Then ΠLz(U)≤ΠLz(Cn),with equality if and only ifU?Cn.

Now we introduce three subsets of the setB(n)as follows:

B1(n)={B1(p,q):p+q=n+1};

B2(n)={B2(p,l,q):p+q+l=n+1};B3(n)={B3(k,l,m):k+l+m=n+1}.

LetGibe any graph fromBi(n)fori=1,2,3. We can get:

ΠLz(G1)=4n+1(n-3)n-1(n-5);

ΠLz(G2)=344n-2(n-3)n-2(n-4)2;

ΠLz(G3)=344n-2(n-3)n-2(n-4)2.

Corollary 6LetBbe a bicyclic graph of ordern≥4,andHbe a graph inB2(n)∪B3(n). Then ΠLz(B)≤ΠLz(H),with equality if and only ifB?H.

ProofUsing Remark 1,we conclude that the graph fromB(n)with maximum multiplicative Lanzhou index must be the graph from the setB1(n)∪B2(n)∪B3(n).

From the above calculation of graphGiinBi(n)withi=1,2,3,we have

Thus we complete the proof of the Corollary 6.

In the end,we summarize the above results and determine the extremal graphs with respect to the multiplicative Lanzhou index fromT(n),U(n)andB(n). Especially we consider the graphs with ?≤n-2,since ΠLz(G)=0 when ?(G)=n-1.

Using Corollaries 1 and 4,we can obtain the Theorem 3.

Theorem 3LetGbe a tree of ordern≥5 with ?(G)≤n-2 different fromSn-1,1andPn. Then

Combining Corollaries 2 and 5. We can obtain the Theorem 4.

Theorem 4LetGbe a unicyclic graph of ordern≥5 with ?(G)≤n-2 different fromC3(Sn-3,P2)andCn. Then

By Corollaries 3 and 6,we can obtain the Theorem 5.

Theorem 5LetGbe a bicyclic graph of ordern≥6 with ?(G)≤n-2 different fromB3(Sn-4,P2)and not inB2(n)∪B3(n).Assume thatBis a graph inB2(n)∪B3(n),then