Abdugheni Tohti,Elkin Vumar

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

0 Introduction

We consider only f i nite,undirected,simple and connected graphs.For the graph def i nitions and notation we follow[2].

LetG=(V,E)be a graph.The distancedG(vi,vj)between two verticesviandvjis def i ned as the length of a shortest path inGconnectinguiandvj.The eccentricity ofvi,denoted byeG(vi)(oreifor short if no confusion occurs),is def i nedthe diameter and radius ofGare def i ned respectively asd(G)=A vertex with eccentricityd(G)(resp.r(G))is called a diametrical vertex(resp.a central vertex).A connected graph is called a self-centered graph(or SC graph for short)if all of its vertices have a same eccentricity.Otherwise,it is called non-self-centered graph.Obviously,a connected graph is an SC graph if and only ifd(G)=r(G).

The concepts of eccentricity and centrality have a lot of applications in the theory of networks and some branches of mathematics,for more results we refer the readers to[3-6]and the references therein.

One of the applications of the eccentricity of a graph is the f i eld mathematical chemistry,where,together with many other topological indices(also known as molecular descriptors),some eccentricity-based topological indices are usedtomodelphysicochemical,pharmacology,toxicology,biologicalandotherpropertiesofchemicalcompounds.For our purpose here,we only give the def i nitions of some eccentricity-based topological indices,for more comprehensive results on the distance-based topological indices we refer the readers to the recent survey[7]

The f i rst,second and third Zagreb eccentricity indices of a graphG([1]and[8])are def i ned respectively as

All the above eccentricity-based indices,especially the third Zagreb eccentricity index,are used to measure the extent of the non-self-centrality of non-self-centered graphs.But,however,for trees,E3does not satisfy some basic properties that other graph invariants have.That is to say,at least for trees,E3is not an ideal one indicating the nonself-centrality of graphs.In view of this,Xu et.al.in[1]introduce a novel graph invariant called non-self-centrality number(NSC number for short)def i ned as

They have studied the basic properties of this novel invariant.It turns out that,compared withE3,it is a better graph invariant for measuring the extent of non-self-centrality of graphs.Among other results,they present the lower and upper bounds onN(G)and characterize the corresponding graphs at which the bounds are attained.However,the extremal graphs given in[1]are not complete.In this note,we present a complete list of extremal graphs with respect to the results in[1].In Section1,we f i rst give some graphs with extremalNSCnumbers,and then present the corrections of some theorems given in[1].Furthermore,as the consequences of our results,we determine the upper bounds onNSCnumber for bicyclic and tricyclic graphs.Finally in Section 2,we determine the lower bound onN(T)for treesTof ordernwith diameterd.

1 Graphs with Large NSC Numbers

First we recall some notations for graphs used in[1].ByPnandCnwe denote a path and a cycle of ordern,respectively.A starlike tree of ordern,denoted byTn(n1,n2,···,nk)withis a tree obtained by attaching at a single vertexkpendent paths of lengthn1,n2,···,nk,respectively.Whenniappearsai>1 times inTn(n1,n2,···,nk),we write asfor short in it.LetCk(n−k)be a graph obtained by attaching at a vertex ofCka pendent path of lengthn−k,and letCk(t1,t2)denote a graph obtained by attaching two pendent paths of lengthst1andt2to two adjacent vertices ofCk.The eccentricity sequence(e.s.for short)of a graphGof ordernwith diameterdand radiusris def i ned as(d(l1),(d−1)(l2),···,(d−i)(li+1),···,(r+i)(lk−i),···,(r+1)(lk−1),r(lk)),wherei≤r−1,k=d−r+1 and(d−i)(li+1)means that there areli+1vertices of eccentricityd−iinG.By def i nition,we have

It is stated in[1]thatPnis the unique graph attaining the maximumNSCnumber among all connected graph,and thatTn(1(2),n−3),C3(n−3)achieve the second maximumNSCnumber fornbeing even and one more graphfornbeing odd,it is also stated that the graphattains the third maximumNSCnumber among all tree of ordern.In this section,we construct some graphs which attain the maximum,the second maximum(resp.the third maximum)NSCnumbers of connected graphs(resp.trees),which are not given in[1].

LetG=(V,E)be a graph of ordernwith diameterdand radiusr.LetP=v1v2···vd+1be a diametrical path inG.Then the eccentricity sequence ofGis

observation 1IfGhas at most two central vertices,then there is a caterpillarCGsuch thatGandCGhave the same eccentricity sequence.More general,for any graph,there is a graph obtained by adding some edges to a caterpillar such that the two graphs have the same eccentricity sequence.

observation 2If the diameterd=d(G)is odd,then one can construct a graphHwith the following eccentricity sequences(2)or(3)and it is easy to check thatN(G)=N(H),where in 3 we havei≤r−1.Note that whend=d(G)is even,then it is not possible to construct any graphHwith eccentricity sequences(2)or(3).

Based on the above observations,one can construct some graphs that are pairwise not isomorphic but have the sameNSCnumber.In fact,in Figure 1,we construct two graphs having the sameNSCnumber asPnforn=2k≥6.Forn=4,we haveN(P4)=N(K4−e).In Figure 2,forn=2k+1≥7,based on graphTn(1(2),n−3),we construct other seven graphs with the sameNSCnumber asTn(1(2),n−3).If we denote the eccentricity sequence ofTn(1(2),n−3)by(1),thenC3(n− 3)has e.s.(1),have e.s.(2)and the other four graphs have e.s.(3l).Forn=5,the connected graphs attaining the second maximumNSCnumber are the six graphs given in the first two rows in Figure2.

Fig 1 Graphs with maximum NSC number when n=2k≥6

Fig 2 Graphs with second maximum NSC number when n=2k+1≥5 and n=2k+1≥7 for

Now we are ready to state some corrections of the results of[1].First we recall some functions inn,which are theNSCnumbers of some extremal graphs.

Theorem 1(Theorem 4.3 in[1]) LetTbe a tree of ordern≥4.The we haveN(T)≤f(n)with equality if and only ifTPn.

For the second maximumNSCnumber of connected graphs and the third maximumNSCnumbers of trees,we have the following two values.

Theorem 2(Theorem 4.4 in[1]) LetTbe a tree of ordern>4 dif f erent fromPn.ThenN(T)≤h(n)with equality if and only ifT?Tn(1(2),n−3).

In the following,we present the corrections of the following four results in[1].The proofs given in[1]are correct except for the characterization for the extremal graphs,hence we omit the proofs.

Theorem 3(cf.Theorem 4.5 in[1]) LetTbe a tree of ordern>5 dif f erent fromPnandTn(1(2),n−3).Then we haveN(T)≤g(n)with equality if and only ifTis isomorphic toTn(1,bc,de)for evennorn=5 and one more graphTn(1,2,n−4)for oddn>7.

Theorem 4(cf.Theorem 4.6 in[1]) LetGbe a connected graph of ordern≥3.Then we haveN(G)≤f(n)with equality if and only ifGis isomorphic toPnfor oddnand two more graphsfor evenn=2k≥6,and one more graphK4−eforn=4.

Theorem 5(cf.Theorem 4.7 in[1]) LetGbe a connected graph of ordern≥5 other thanPn.Then we haveN(G)≤h(n)with equality if and only if

(a)G∈{Tn(1(2),n−3),C3(n−3)}for evenn;

(b)G∈{Tn(1(2),n−3),C3(n−3),forn=2k+1=5;

(c)G∈{Tn(1(2),n−3),C3(n−3),for oddn=2k+1≥7.

In the following Corollary 1 we present the upper bounds on theNSCnumber for unicyclic graphs.For graphssee Figures 1 and 2.

corollary 1(cf.Corollary 4.8 in[1]) For any unicyclic graphGof ordern≥5 we have

(a)N(G)≤f(n)with equality if and only iffor evenn=2k;

(b)N(G)≤h(n)with equality if and only ifG∈{C3(n−3),C3(),}for oddn=2k+1.

Based on the above results,we obtain the upper bounds for bicyclic graphs.Note that Corollary 2 is a new result.For graphsand(i=1,2,3)see Figures 1 and 2.

corollary 2For any bicyclic graphGof ordern≥5 we have

(a)N(G)≤f(n)with equality if and only iffor evenn=2k;

(b)N(G)≤h(n)with equality if and only ifG∈for oddn=2k+1=5;

(c)N(G)≤h(n)with equality if and only iffor oddn=2k+1≥7.

Finally,we obtain the upper bound for tricyclic graphs of odd ordern=2k+1≥7.

corollary 3For any tricyclic graphGof odd ordern=2k+1≥7 we haveN(G)≤h(n)with equality if and only if

2 Lower Bound for Trees of Order n and Diameter d

In[1],the authors present the upper bound onNSCnumber for trees of ordernand diameterd.In this section,we determine the lower bound onNSCnumber for such trees.

A caterpillar,denoted by(a2,a3,...,ad)with=n−d−1,is a tree obtained from a diametrical pathP=vv···vby attachinga≥ 0 pendent vertices to the vertexvfori=2,3,···,d.Fori=0,1,2,3 andd=4k+i,d+112d+1iiletC(n,k,i)be a caterpillar obtained by attachingn−d−1 vertices at the vertexvk+twitht=1+in a diametrical pathP4k+i+1=v1v2···v4k+i+1.Ford=4k+i,we def i ne four functions asfi(n)=+[2k2+(i+1)k](n−4k−1−i)fori=0,1 andfi(n)=+[2(k+1)2+(i−3)k](n−4k−1−i)fori=2,3.

By a routine calculation,we obtain thatN(C(n,k,i))=fi(n),i=0,1,2,3.Let Cn,dbe the set of caterpillars of ordernand diameterd.

Theorem 6Letd=4k+ifori=0,1,2,3 withk≥1,d≤n−2.Then for any treeTof ordernand diameterd,we haveN(T)≥fi(n)with equality ifT?C(n,k,i).

ProofBy Observation 1,it is not difficult to deduce that the extremal tree must be a caterpillar.Moreover,we only prove the cased=4k,the other three cases can be proved by a similar argument.LetTbe any caterpillar of ordernand diameterd=4kwith a diametrical pathP4k+1=v1v2···v4k+1.Let the eccentricity sequence ofTbewhere=n−4k−1=n−d−1 andes=e(vs)=e(v4k−s+2)=4k+1−sfors=1,2,···,2k+1.We shall prove that∇=N(T)−N(C(n,k,0))≥0.

Case 1li=n−d−1 andlj=0 forj,i.ThenThas the eccentricity sequence

Denoted byli=l=n−d−1,by def i nition,we have

Similarly,we have

Now we have

Then,∇=2l[i−(k+1)][2i−(2k+1)]≥0 with equality if and only ifi=k+1.

Case 2lt1,0,lt2,0 for some distinctt1,t2.

Note thatl=by the formula ofN(T)in Case 1,we haveN(T)=N(P2k+1)+By replacinglwithwe haveN(C(C(n,k,0))=N(P2k+1)+−e2k+1|.

Def i ne ∇i=2li[i−(k+1)][2i−(2k+1)]fori=1,2,···,2k.By the result obtained in Case 1,we infer that∇i=0 if and only ifli=0 ori=k+1.Then we have∇=N(T)−N(C(n,k,0))=+li|ei−e2k+1|−ej|+li|ek+1−e2k+1|)]+≥0 with equality if and only iflk+1=n−d−1,lj=0 forj,k+1.The proof is now complete.

References：

[1]Xu K X,Das K C,Maden A D.On a novel eccentricity-based invariant of a graph[J].Acta Mathematica Sinica English,2016,32(12):1477-1493.

[2]Bondy B A,Murty U S R.Graph Theory[M].London:Springer,2008.

[3]Buckley F.Facility location problems[J].College Mathematics Journal,1987,18(1):24-32.

[4]Chartrand G,Gu W,Schultz M,et al.Eccentric graphs[J].Networks,1999,34:115-121.

[5]Hage P,Harary F.Eccentricity and centrality in networks[J].Social Networks,1995,17(1):57-63.

[6]Krnc M,krekovski R.Group centralization of network indices[J].Discrete Applied Mathematics,2015,186(C):147-157.

[7]Xu K,Liu M,Das K C,et al.A Survey on Graphs Extremal with Respect to Distance–Based Topological Indices[J].Match Communications in Mathematical in Computer Chemistry,2014,71(3):461-508.

[8]VukieviD,Graovac A.Note on the comparison of the first and second normalized zagreb eccentricity indices.[J].Acta Chimica Slovenica,2010,57(3):524-528.