The Hyper-Wiener Index of Graphs with Radius Two?

HE Huan-ying,AN Xin-hui

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

Abstract: Let G be a connected graph,the hyper-Wiener index WW(G)of the graph G is defined as WW(G)=where d(u,v)denotes the distance between u and v of G.In this paper,we discuss mainly the hyper-Wiener index of trees with radius two and give the calculating formula.We also characterize graphs with the maximum hyper-Wiener index among all graphs of order with radius two,where t is some positive integer.

Key words:hyper-Wiener index;Distance;Radius

0 Introduction

Throughout this paper we consider simple connected graphs.We refer to[1]for unexplained terminology and notations.LetG=(V(G),E(G))be a simple connected graph withn=|V(G)|.For two verticesthe distancedG(u,v)betweenuandvinGis the length of a shortest path connectinguandvinG.The eccentricityecc(v)of a vertexvinGis the largest distance fromvto another vertex ofG,i.e.max{d(v,w)|w∈V(G)}.The diameter ofGis the maximum eccentricity inG,denoted bydiam(G).Similarly,the radius ofGis the minimum eccentricity inG,denoted byrad(G).

A vertexv∈V(G)is called a center ofGifecc(v)=rad(G).It is well-known that every tree has either exactly one center or two adjacent centers.The Wiener index of a graphGdenoted by is defined asKlein et al[2].extended the definition for all connected graphs,as a generalization of the Wiener index.The hyper-Wiener index of a graphGis defined as

The hyper-Wiener index is studied for various class of graphs,such as trees[3],unicyclic graphs[4],bicyclic graphs[5],graphs with matching number[6].For the mathematical properties of hyper-Wiener index and its applications in chemistry,we encourage the readers to consult[7,8].

Obviously,complete graphsKnhas the minimum hyper-Wiener index among all connected graphs of ordern(and so among all graphs of ordernwith radius one).For the case of radius two,it is not hard to prove that the extremal graphGnshould be the following:ifnis even,whereMis a perfect matching;ifnis odd,whereFis a maximum matching ofKnandeis an edge incident with the vertex of degreen?1 inKnF.

Chen[9]characterize graphs with the maximum Wiener index among all graphs of order n with radius two.In the paper,we discuss mainly the hyper-Wiener index of trees with radius two and give the calculating formula.We also characterize graphs with the maximum hyper-Wiener index among all graphs of orderwith radius two,wheretis some positive integer.

1 Preliminaries

Lemma 1For any connected graphG,there exists a spanning tree ofTofG,such thatrad(T)=rad(G),andWW(T)≥WW(G).

proofLetube a center ofG,andTbe a BFS-tree ofGrooted atu.The treeTis one,as we desired.

By Lemma 1,the graph with the maximum hyper-Wiener index among all graphs with radius 2 must be a tree.

The path numberp(G)of a graphGis defined to be the maximum cardinality of a subset of vertices that induces a path.Erd?os et al[10]showed that for any connected graphG,p(G)≥2rad(G)?1.

Lemma 2[9]For a treeGwith radiusr,2rad(G)≤p(G)≤2rad(G)+1.

Lemma 3IfTbe a tree of ordernwith the maximum hyper-Wiener index among all trees with radius two.Ifn=4,thenandp(T)=5 otherwise.

proofIfn=4,the result is trivial.So,letn≥5.By lemma 2,4≤p(T)≤5.By contradiction,suppose thatp(T)=4.LetP=v1v2v3v4be a path on four vertices inT.Every other vertex not onPmust be adjacent tov2orv3.Without loss of generality,letandxbe a pendent vertex adjacent tov3.SetIt is easy to check thatWWcontradicting the choice ofT.

Lemma 4[9]LetTbe a tree,then

(1)the center ofTis a vertex or two adjacent vertices,

(2)the center ofTis one vertex if and only if diam(T)=2 rad(T).

The above two Lemmas assert that ifTis a tree of ordernwith the maximum hyper-Wiener index among all trees of order at least five with radius two,thenThas the unique center.We denote byTn,t(n1,...,nt)the tree of ordernwith radius two and unique centervcsuch thatd(vc)=t,N(vc)={v1,...,vt}andd(vi)=ni+1.In particular,S(n,t)=Tn,t(n1,...,nt),with|ni?nj|≤ 1 for anyi,j.That is,S(n,t)denote the tree of ordernwith unique centervcandd(vc)=t,the leaves are balanced as possible as on each branch of the tree.

Lemma 5LetT=Tn,t(n1,...,nt)be the tree as described above,then

proofLetxi=|{(u,v)|u,v∈V(T),d(u,v)=i}|.Hence

By simple calculation,

Lemma 6Letandn1?n2≥2,then

By lemma 5,we derived

Corollary 1Letnandtbe two positive integers such thatn>t+2 and 1+t+kt≤n<1+t+(k+1)tfor some integerk≥0,and letp=n?1?t?kt.ThenWW(S(n,t)andp=0,then

proofBy the notation of previous Lemma,inS(n,t),the number ofequal tok+1 ispand the number ofequal tokist?p.So,by Lemma 5

Ifandp=0,by the above formula

Moreoverand

This proves

2 Main results

Lemma 7Letnandtbe two positive integers such thatn>t+2 andn≥5.Define a functionf(t)=10n2+then it has the only maximal pointandf(t)has only a roott0fort∈ [2,n],

proofIts derivativeLetwith the same root and same monotonicity.So,we only need considerg(t).

By the zero point theorem，g(t)at least has a root fort∈(?∞,0],fort∈(0,n]and fort∈(n,+∞),respectively.Sinceg(t)is three cubed,so it has only three roots.Henceg(t)has only a root fort∈(0,n],so we admitf(t)has only a roott0fort∈(0,n].

since

So by the zero point theorem，

Sinceg(t)=6t2+14t? 16nt≤ 6t2+14t? 16t2= ?10t2+14t.We admitg(t)<0 fort≥ 2.Henceg(t)is monotonic decreasing fort∈ [2,n]，andg(t0)=0.That is

Sot0is the only maximal point forf(t)witht∈[2,n],f(t0)≥f(t)fort∈[2,n].

For a clear understanding of our theorem as follow,we make some remarks.Iffor some positive integert0,thenBy Corollary 1,WW(S(n,t0))=WW(S(n,t0+1)).

Theorem 1LetTbe a tree with the maximum hyper-Wiener index among all trees of ordernwith radius two.Iffor some positive integert0,then√

proofBy Lemma 3,letvcbe the unique center ofT,and letd(vc)=t.SetN(vc)={v1,v2,···,vt},and|N(vi)vc|=nifor 1≤i≤t.Corollary 1 assert that|ni?nj|≤1 for anyi,j,and thusTS(n,t)for somet.To showt=t0,as specified in the theorem,it suffices to show thatWW(S(n,t0))>WW(S(n,t)for anytt0.By Corollary 1,

wherewe have

By the definition ofandp=0.

Case 1t∈[2,t0?1]

Case 2t∈[t0+2,n?1)

We have

SoWW(S(n,t0))>f(t0+2).It follows thatWW(S(n,t0))>f(t0+2)≥f(t)≥WW(S(n,t)).

By Corollary 1,ifthenWW(S(n,t0))=WW(S(n,t0+1)).It follow thatThus we finish the proof.

LetTbe a tree with the maximum hyper-Wiener index among all trees of ordern,iffor some positive integert,we conjecture thatFor example,ifn=1060,thent0=31,andWW(S(n,t0))>WW(S(n,t0+1)),andIfn=1600,thent0=37,WW(S(n,t0))