Distance and Eccentric sequences to bound the Wiener index, Hosoya polynomial and the average eccentricity in the strong products of graphs

Discrete Applied Mathematics 263 (2019) 105–117 Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam Distance and Eccentric sequences to bound the Wiener index, Hosoya polynomial and the average eccentricity in the strong products of graphs✩ Rocío M. Casablanca*, Peter Dankelmann article info Article history: Received 3 October 2017 Received in revised form 15 May 2018 Accepted 5 July 2018 Available online 16 August 2018 Keywords: Wiener index Average distance Average eccentricity Wiener polynomial Hosoya polynomial Strong product Distance sequence Distance distribution abstract This paper is concerned with the strong product G⊠Hof two graphs, Gand H, and bounds on the Wiener index, Hosoya polynomial and the average eccentricity in this family of graphs. We first introduce the distance sequence of a connected graph. It is defined as the sequence of the distances between all unordered pairs of vertices. We prove that the distance sequence of any connected graph of given order and size is dominated by the distance sequence of the so-called path-complete graph. This is the main tool to prove general results as, among others, that, if Gis a connected graph of given order and size, then the Wiener index of G⊠H, for every fixed connected graph H, and the Hosoya polynomial W(G,x), for every x∈Rwith x≥1, are maximised if Gis a path-complete graph. We also investigate the average eccentricity of G⊠H. We show that for fixed H, and Gchosen from among all connected graphs of given order n, it is maximised if Gis a path of the same order. We also determine a graph Gn,δ of order nand minimum degree δsuch that for every connected graph Gof order nand minimum degree δ, the average eccentricity of G⊠Hnever exceeds the average eccentricity of Gn,δ ⊠Hby more than 3. ©2018 Elsevier B.V. All rights reserved. 1. Introduction Distances between the different points of a network are of great importance in the analysis of the network, and so distance measures are important indicators for communication efficiency in a network. In this paper we consider two distance measures: the Wiener index and the average eccentricity. The Wiener index of a connected graph Gwith vertex set Vis defined by W(G)=∑ {u,v}⊆V d(u, v), where d(u, v) denotes the distance between uand vvertices in Gand the sum is taken over all unordered pairs of vertices. The Wiener index found numerous applications in chemistry [25] and it is currently much investigated (see for example [1,14,19,20]). The Wiener index is closely related to the average distance µ(G) of G, defined as (|V| 2)−1W(G). The Hosoya polynomial (also called Wiener Polynomial), introduced by Hosoya in [18] is the polynomial W(G,x)=∑{u,v}⊆Vxd(u,v), which has been and recently studied [8,9,26,30]. ✩This research was supported by the Ministry of Economy and Competitiveness, Spain, under project MTM2014-60127-P, the University of Seville, Spain and the University of Johannesburg, South Africa. *Corresponding author. E-mail addresses: [email protected] (R.M. Casablanca), [email protected] (P. Dankelmann). https://doi.org/10.1016/j.dam.2018.07.009 0166-218X/©2018 Elsevier B.V. All rights reserved. 106 R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 The average eccentricity (see, for example, [6]) is defined as the arithmetic mean of the eccentricities of the vertices, avec(G)= |V|−1∑ v∈V ecc(v), where the eccentricity ecc(v) of a vertex vis defined as the distance to a vertex farthest from v. Graph products play an important role in the design of networks since they often allow us to build larger versions of a network preserving certain desirable properties. For designing large-scale interconnection networks, the graph products are useful methods to obtain large graphs from smaller ones whose invariants can be easily calculated. For more information on this topic we refer the reader to the book by Hammack, Imrich and Klavžar [16]. We have focused on the strong product of graphs, which is one of the classical graph products, and there is an extensive literature on it. The strong product G ⊠Hof two connected graphs Gand His the graph with vertex set V(G)×V(H) in which two vertices (a,u) and (b, v) are adjacent if a=band uv∈E(H), or ab ∈E(G) and u=v, or ab ∈E(G) and uv∈E(H). From the definition, it clearly follows that the strong product of two graphs is commutative and that it is connected if and only if both graphs are connected. While the Wiener index of the cartesian product and some other products of graphs can be expressed relatively easily in terms of the Wiener index and other basic information of the two component graphs (see [32]), expressing the Wiener index of the strong product of graphs seems to be less simple (see [3,23]). The same holds true for the average eccentricity (see [7,12]). Hence it is reasonable to consider bounds on the Wiener index and the average eccentricity of the strong product of graphs. The following basic result on the Wiener index has been proved independently by Doyle and Graver [10], Lovász [22] and Plesník, [24]. Theorem 1 ([10,11,22,24]).Let G be a connected graph of order n. Then W(G)≤n(n+1)(n−1) 6. Equality holds if and only if G is a path. The starting point of our investigations is a generalisation by Casablanca, Favaron and Kouider [3], showing that for every fixed, connected graph H, the Wiener index of G⊠H, where Granges over all connected graphs of given order n, is maximised if Gis the path Pn. The special case H=K1in Theorem 2 is Theorem 1. Theorem 2 ([3]).Let H be a connected graph. If G is a connected graph of order n, then W(G⊠H)≤W(Pn⊠H), with equality only if G is a path. We strengthen this result in different ways. In Section 3we present some results on the distance sequence of a graph, defined as the non-decreasing sequence of the distances between all unordered pairs of vertices. These form the basis for the following two sections. In Section 4we generalise Theorem 2, showing that if we prescribe not only the order but also the size of G, then for every fixed, connected graph H, the Wiener index of G⊠His maximised if Gis the so-called pathcomplete graph PKn,m, defined in Section 2. We also strengthen Theorem 2 for Gbeing a 2k-connected graph. In this case W(G⊠H) is maximised if Gis the kth power of a cycle. We also determine graphs Gthat minimise W(G⊠H) for every fixed, connected graph Hfor Gbeing a graph of given order and size, a tree, a planar graph, an outerplanar graph, a graph with no clique Krwhere r∈N, or a graph of given order and diameter. In Section 5we apply the results from Section 2to derive some properties of the Hosoya polynomial W(G,x). We show that every connected graph Gand for x∈Rwe have W(G,x)≤W(Pn,x) if x≥1 and W(G,x)≥W(Pn,x) for x≤1. We show similar relations with Pnreplaced by PKn,mif Ghas order nand size m, with Pnreplaced by Ck nif Ghas order nand is 2k-connected. We also show that the opposite inequalities hold for certain graphs. In Section 6we obtain results for eccentric sequences of graphs, similar to those for the distance sequence in Section 3. In the final section, Section 7we obtain results for the average eccentricity of G⊠H, similar to those for the Wiener index in Section 4by determining graphs Gthat maximise avec(G⊠H) where Gis a graph of given (i) order, (ii) order and (even) connectivity, and (iii) order and minimum degree. 2. Notation Our notation is as follows. If Gis a graph, then we denote its vertex and edge set by V(G) and E(G), respectively. We use nG and mGfor the order and size of G, respectively. If vis a vertex, then NG(v) and NG[v]are the neighbourhood of v, i.e., the set of vertices adjacent to v, and the closed neighbourhood, i.e., the set NG(v)∪{v}, respectively. The distance dG(u, v) between two vertices uand vis the minimum number of edges on a (u, v)-path in G. The diameter of G,d(G), is the maximum distance between two vertices of G. If vis a vertex of Gand k∈N, then Nk(v) denotes the set of vertices at distance exactly kfrom v. By N≤k(v) we mean the set ⋃k i=1Ni(v). The distance between a vertex vand a set W⊆V(G) is defined as minw∈WdG(v, w). Let degG(v) be the degree of v, i.e., the cardinality of NG(v), and δ(G) is the minimum degree of G. If there is no ambiguity we often drop the subscript or argument G. R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 107 By Pn,Cn,Knand Ka,bwe denote the path, cycle, complete graph and complete bipartite graph with partite sets of cardinality aand b, respectively, of order n. The graph with nvertices and no edges is denoted by Kn. The kth power Gk of a graph Gis the graph with vertex set V(G) in which two vertices are adjacent if their distance is not more than k. If G1and G2are two graphs, then their sum G1+G2(also called their join) is the graph obtained from their disjoint union by adding edges joining every vertex of G1to every vertex of G2. If X=(x1,...,xm) and Y=(y1,...,yn) are two sequences of integers and c∈N, then the sequence (x1,...,xm,y1,..., yn) is the concatenation of Xand Y, denoted by X◦Y, and Xcdenotes the sequence obtained from Xby repeating every entry ctimes, (x1,x1,...,x1,x2,x2,...,x2,...,xm,xm,...,xm), and cX is the sequence (cx1,...,cxm). If m=n, then X+Yis the sequence (x1+y1,...,xm+ym). 3. Distance sequences of graphs The main tool in our investigations of the Wiener index of the strong product of graphs is the distance sequence, defined below. It is closely related to the distance distribution of a graph, which was introduced by Buckley and Superville [2] and further investigated in [4,27,31]. Definition 1. Let Gbe a connected graph of order n. The distance sequence D(G) is the non-decreasing sequence (d1,d2,...,d(n 2)) of the distances between all unordered pairs of distinct vertices of G. If Ais a set of pairs of vertices of G, then D(G)|Adenotes the non-decreasing sequence of the distances between all the unordered pairs of vertices in A. The distance degree of a vertex vof G, denoted by D(G, v), is the non-decreasing sequence of the distances between vand all other vertices of G. Definition 2. Let A=(a1,a2,...,ak) and B=(b1,b2,...,bk) be two sequences of the same length. We say that A dominates Bif ai≥bifor i=1,2,...,k, and we write A≥B. In this section we show that certain graphs that are known to have maximum Wiener index among all graphs of given order in a particular class of graphs possess a much stronger property: their distance sequence dominates, or is dominated by, the distance sequence of every connected graph of the same order within their particular class of graphs. We make extensive use of this property in Sections 4and 5. Our first result of this kind shows that the distance sequence of a path-complete graph (defined below) dominates the distance sequence of all connected graphs of the same order and size. Path-complete graphs were introduced by Harary in [17]. Definition 3 ([17]).A graph is path-complete if it can be obtained from the union of a path and a clique by joining one end of the path to at least one vertex of the clique. For given n,m∈Nwith n−1≤m≤(n 2)there is a unique path-complete of order nand size m, which is denoted by PKn,m. Šoltés [28] showed that the path-complete graph PKn,mhas maximum average distance among all connected graphs of order nand size m. A simple expression for the Wiener index of PKn,mwas given by Gutman and Šoltés in [15]. In his proof, Šoltés made use of a stronger property of path-complete graphs, which we use to show that the distance sequence of PKn,m dominates that of any connected graph of order nand size m. For k∈Ndefine sk(G) to be the number of all unordered pairs of non-adjacent vertices of Gat distance at most k. Lemma 1 ([28]).Let G be a connected graph of order n, size m and diameter d, where d ≥3. Then, for all k with 2≤k≤d−1, sk(G)≥sk(PKn,m). Lemma 2. If G is a connected graph of order n and size m, then D(G)≤D(PKn,m). Proof. Let d=diam(G) and let D(G)=(d1,d2,...,d(n 2)) and D(PKn,m)=(d′ 1,d2,...,d′ (n 2)). So it suffices to show that di≤d′ ifor i=1,2,...,(n 2). (1) Suppose to the contrary that there exists j∈ {1,2,...,(n 2)}with dj>d′ j. Let jbe the smallest number with this property. Since both, Gand PKn,mhave size m, we have di=d′ i=1 for i=1,2,...,m, and thus j>mand d′ j≥2. This implies in particular that d≥3. It is immediate from the definition of skthat for kwith 2 ≤k≤d−1, di=k⇔m+sk−1(G)+1≤i≤m+sk(G).(2) 108 R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 Now let dj=kand d′ j=k′<k. From (2) we get m+sk−1(G)+1≤j≤m+sk(G) and m+sk′−1(PKn,m)+1≤j≤m+sk′(PKn,m). Comparing the left hand side of the first and the right hand side of the second of these inequalities, we conclude that sk−1(G)+1≤sk′(PKn,m). By k′≤k−1 and the fact that the sequence si(PKn,m) is increasing in i, we get sk−1(G)<sk−1(PKn,m). Since 2 ≤d′ j=k′≤k−1, as observed above, we have a contradiction to Lemma 1. This proves (1).□ Corollary 1. Let G be a connected graph of order n. Then D(G)≤D(Pn). Proof. Let Tbe a spanning tree of G. Clearly, D(G)≤D(T). Applying Lemma 2 with m=n−1 and noting that PKn,n−1=Pn we get D(T)≤D(Pn). Combining these two inequalities yields the corollary. □ Remark 1. It is natural to ask if it is true that, whenever Gand G′are connected graphs of the same order, then D(G)≤D(G′) if and only if W(G)≤W(G′). While clearly D(G)≤D(G′) implies W(G)≤W(G′), the converse is not true in general. Consider the graphs Fand F′below: FF′ Then D(F)=(3,27,17) and D(F′)=(210,15), and so W(F)=24 and W(F′)=25. Clearly, W(F)≤W(F′) but D(F)≤ D(F′). Lemma 3. Let G be a 2k-connected graph of order n, where k ∈N. Then D(G)≤D(Ck n). Proof. It suffices to show that for every vertex vof Gand every vertex wof Ck n, D(G, v)≤D(Ck n, w). Let vbe an arbitrary vertex of Gand let D(G, v)=(a1,a2,...,an−1). Since Gis 2k-connected, vhas at least 2kvertices at distance ifor i=1,2,...,ecc(v)−1. It follows that a1,a2,...,a2k≤1, a2k+1,a2k+2,...,a4k≤2, a4k+1,a4k+2,...,a6k≤3 and so on. Hence D(G, v)≤(1,2,...,⌈n−1 2k−1⌉)2k◦(⌈n−1 2k⌉)b where b=n−1−2k⌈n−1 2k−1⌉. Let wbe an arbitrary vertex of Ck n. It is easy to verify that whas exactly 2kvertices at distance ifor i=1,2,...,⌈n−1 2k−1⌉ and the remaining vertices have distance ⌈n−1 2k⌉. It follows that D(Ck n, w)=(1,2,...,⌈n−1 2k−1⌉)2k◦(⌈n−1 2k⌉)b, where b=n−1−2k⌈n−1 2k−1⌉as above. Hence D(G, v)≤D(Ck n, w), as desired. □ We now present graphs of given order and diameter whose distance sequence is dominated by every graph with the same order and diameter. R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 109 Definition 4. Let Gbe a graph of order nand diameter d. Let Gn,dbe the graph obtained from the disjoint union of a path Pd+1:v0, v1, . . . , vdand a clique Kn−d−1by joining every vertex in the clique to v⌊d/2⌋−1,v⌊d/2⌋and v⌊d/2⌋+1. Lemma 4. Let G be a graph of order n and diameter d and Gn,dbe the graph described in Definition 4. Then D(G)≥D(Gn,d). Proof. Let v0and vdbe two vertices of Gat distance d, and let P:v0, v1, . . . , vdbe a shortest (v0, vd)-path in G. We partition the set of all unordered pairs of vertices of Ginto three sets, A,Band C, where Ais the set of pairs of vertices that are both on P,Bthe set of pairs of vertices that are both not on P, and Cthe set of pairs where one vertex is on Pand the other one is not. Clearly, D(G)|A=D(P)=D(Pd+1).(3) and D(G)|B≥(1)(n−d−1 2).(4) We now consider the distances between pairs in C. Let u∈V(G)−V(P) and let k:= dG(u, v0). Then dG(u, vk)≥1. Since d(u, vi)≥ |k−i|for i=0,1,...,d, the distances from uto vk−1, vk−2, . . . , v0are at least 1,2,...,k, and the distances for uto vk+1, vk+2, . . . , vdare at least 1,2,...,d−k. Hence, with j:= min(k,n−k) and j′:= max(k,n−k), the distances from uto the vertices of Pare at least (1,1,1,2,2,3,3,...,j,j,j+1,j+2,...,j′−1,j′). Observe that the latter dominates (1,1,1,2,2,3,3,...,n−2 2,n−2 2,n 2) when nis even, but in the case that nis odd, (1,1,1,2,2,3,3,...,n−1 2,n−1 2). Hence D(G, v)≥⎧ ⎪ ⎨ ⎪ ⎩ (1,1,1,2,2,3,3,...,n−2 2,n−2 2,n 2) if nis even, (1,1,1,2,2,3,3,...,n−1 2,n−1 2) if nis odd. =1◦D(Pd+1,c),(5) where cis a central vertex of the path Pd+1. Now for Gn,d,(3),(4), and (5) hold with equality. Let A′,B′and C′be the set of all unordered pairs of vertices of Gn,dthat have both vertices are in Pd+1, both vertices are in Kn−d−1, and one vertex in Pd+1and one vertex in Kn−d−1, respectively. Hence D(Gn,d)|A′≤D(G)|A,D(Gn,d)|B′≤D(G)|B,D(Gn,d)|C′≤D(G)|C. Hence we conclude that D(Gn,d)≤D(G), as desired. □ We conclude this section by showing that among the graphs of given order and size, the distance sequences of those of diameter two are dominated by all such graphs. Applying this result to some classes of graphs, we get that in those classes, a graph that has maximum size relative to its order and also diameter at most two, has a distance sequence that is dominated by every other graph of the same order in this class. Proposition 1. Let G be a connected graph of order n and size not more than m. If G′is a graph of order n, size m, and diameter at most two, then D(G)≥D(G′), with equality if and only if diam(G)≤2and G has size m. Proof. Let D(G)=(d1,d2,...,d(n 2)). Since Ghas size not more than m, we have d1,d2,...,dm≥1 and dm+1,dm+2. . . , d(n 2) ≥2. Hence, D(G)≥(1)m◦(2)(n 2)−m, Clearly, equality holds if and only if diam(G)≤2 and Ghas size m. The proposition follows. □ Corollary 2. Let G be a connected graph of order n. (a) If G is a tree then D(G)≥D(K1,n−1). (b) If G is a planar graph then D(G)≥D(K2+Pn−2). (c) If G is an outerplanar graph then D(G)≥D(K1+Pn−1). (d) If G has no k-clique then D(G)≥D(Tn,k), where Tn,kis the Turán graph, i.e., the balanced, complete (k−1)-partite graph. 110 R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 4. Bounds on the Wiener index of the strong product Several upper and lower bounds on the Wiener index of graphs of given order with certain properties are known. The following upper and lower bounds are relevant for this section. The graphs in these two theorems were defined in Section 3. Theorem 3. Let G be a connected graph of order n. (a) ([28]) If G has size m then W(G)≤W(PKn,m). (b) ([13]) If G is 2k-connected then W(G)≤W(Ck n). Theorem 4. Let G be a connected graph of order n. (a) ([24]) If G has diameter d, then W(G)≥W(Gn,d). (b) ([24]) If G has size m then W(G)≥n(n−1) −m, with equality if diam(G)≤2. (c) ([24]) If G is a tree then W(G)≥W(K1,n−1). (d) ([24]) If G is a planar graph then W(G)≥W(K2+Pn−2). (e) ([24]) If G is an outerplanar graph then W(G)≥W(K1+Pn−1). (f) ([24]) If G has no k-clique then W(G)≥W(Tn,k). In this section we use the results of Section 3to show that the graphs in Theorems 3 and 4do not only maximise or minimise W(G), but have the stronger property of maximising or minimising the strong product with any connected graph in the same sense as in Theorem 2. The following Lemma allows us to derive these results from the results on distance sequences in the preceding section. Lemma 5. Let G and G′be two connected graphs of the same order. If D(G)≥D(G′)then W(G⊠H)≥W(G′⊠H) for every connected graph H. If equality holds for some connected graph H, then we have D(G)=D(G′). Proof. Let H,Gand G′be as in the hypothesis of the lemma. Let nbe the order of Gand G′, and let D(G)=(d1,d2,...,d(n 2)) and D(G′)=(d′ 1,d′ 2,...,d′ (n 2)). Then di≥d′ ifor i=1,2,...,(n 2). Making use of the fact that for a,b∈V(G) and u, v ∈V(H), we have dG⊠H((a,u),(b, v)) =max(dG(a,b),dH(u, v)), we obtain W(G⊠H)=1 2∑ a,b∈V(G)∑ u,v∈V(H) dG⊠H((a,u),(b, v)) =1 2∑ a,b∈V(G)∑ u,v∈V(H) max(dG(a,b),dH(u, v)) =nW(H)+ (n 2) ∑ i=1∑ u,v∈V(H) max(di,dH(u, v))(6) ≥nW(H)+ (n 2) ∑ i=1∑ u,v∈V(H) max(d′ i,dH(u, v))(7) =1 2∑ a,b∈V(G′)∑ u,v∈V(H) max(dG′(a,b),dH(u, v)) =1 2∑ a,b∈V(G′)∑ u,v∈V(H) dG′⊠H((a,u),(b, v)) =W(G′⊠H), as desired. To see that (6) holds note the following. If (a,u),(b, v) are two vertices of G⊠Hwith a= b, then the vertices are in distinct copies of H, and so dG⊠H((a,u),(b, v)) appears twice in the sum ∑a,b∈V(G)∑u,v∈V(H)max(dG(a,b),dH(u, v))but only once in ∑(n 2) i=1∑u,v∈V(H)max(di,dH(u, v)). If (a,u) and (b, v) are two vertices of G⊠Hwith a=b, then dG⊠H((a,u),(a, v)) is not counted in ∑(n 2) i=1∑u,v∈V(H)max(di,dH(u, v))but in nW(H). Assume that W(G⊠H)=W(G′⊠H) for some connected graph H. Then we have equality in (7), and so max(di,dH(u, v)) = max(d′ i,dH(u, v)) for all u, v ∈V(H) and all i. If uv∈E(H), then dH(u, v)=1, and so di=d′ ifor all i. Hence D(G)=D(G′), as desired. □ R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 111 Remark 2. It is natural to ask if it is true that whenever Gand G′are connected graphs with W(G)≤W(G′), then W(G⊠H)≤W(G′⊠H) for every connected graph H. The graphs Fand F′defined in Section 3show that this is not the case. As observed, we have W(F)<W(F′). Substitute Ffor G,F′for G′, and F′for H. But it is easy to check that D(F⊠F′)= (336,2452,1142) and D(F′⊠F′)=(2520,1110) and so W(F⊠F′)=1154 and W(F′⊠F′)=1150, implying that W(F⊠F′)> W(F′⊠F′). Lemma 5 combined with Lemmas 2–4,Proposition 1 and Corollary 2 yields the following theorems. Theorem 5. Let H be a connected graph. If G is a connected graph of order n and size m, then W(G⊠H)≤W(PKn,m⊠H). The special case m=n−1 yields Theorem 2. Theorem 6. Let H be a connected graph. If G is a 2r-connected graph of order n where r ∈N, then W(G⊠H)≤W(Cr n⊠H). Theorem 7. Let G be a connected graph of order n and diameter d and Gn,dbe the graph described in Definition 4. Then, for every connected graph H, W(G⊠H)≥W(Gn,d⊠H). Theorem 8. Let G be a connected graph of order n and size not more than m. If G′is a graph of order n, size m, and diameter at most two, then W(G⊠H)≥W(G′⊠H). with equality if and only if diam(G)≤2. Corollary 3 (a).Let T be a tree of order n. Then for every connected graph H, W(T⊠H)≥W(K1,n−1⊠H). (b) Let G be a connected planar graph of order n, where n ≥5. Then for every connected graph H, W(G⊠H)≥W((K2+Pn−2)⊠H). (c) Let G be a connected outerplanar graph of order n, where n ≥5. Then for every connected graph H, W(G⊠H)≥W((K1+Pn−1)⊠H). (d) Let k ∈Nwith k ≥3. Let G be a connected graph of order n with no complete subgraph of order k. Then for every connected graph H, W(G⊠H)≥W(Tn,k⊠H). 5. On the Hosoya polynomial of graphs with certain properties In this section we apply the results on the distance sequence proved in Section 2to Hosoya polynomials. The key observation on which the results in this section rest is the following lemma. Lemma 6. Let G and G′be two connected graphs of the same order. If D(G)≥D(G′)then, for x ∈R, W(G,x)≥W(G′,x)if x ≥1, W(G,x)≤W(G′,x)if 0≤x≤1. Proof. Let Gand G′be connected graphs of order nwith distance sequence (d1,d2,...,d(n 2)) and (d′ 1,d′ 2,...,d′ (n 2)), respectively. By the hypothesis of the theorem we have di≥d′ ifor i=1,2,...,(n 2). Hence for x∈R, W(G,x)−W(G′,x)=(n+ (n 2) ∑ i=1 xdi)−(n+ (n 2) ∑ i=1 xd′ i) = (n 2) ∑ i=1 (xdi−xd′ i). Hence, since di≥d′ iwe have xdi−xd′ i≥0 for x≥1, and xdi−xd′ i≤0 for 0 ≤x≤1, and the lemma follows. □ 112 R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 Applying Lemma 6 to the results in Chapter 2, specifically to Lemmas 2–4,Proposition 1 and Corollaries 1 and 2we obtain the following results. Theorem 9. For every connected graph G of order n we have W(G,x)≤W(Pn,x)for all x ∈Rwith x ≥1, W(G,x)≥W(Pn,x)for all x ∈Rwith 0≤x≤1. Theorem 10. For every connected graph G of order n and size m we have W(G,x)≤W(PKn,m,x)for all x ∈Rwith x ≥1, W(G,x)≥W(PKn,m,x)for all x ∈Rwith 0≤x≤1. Theorem 11. For every 2k-connected graph G of order n we have W(G,x)≤W(Ck n,x)for all x ∈Rwith x ≥1, W(G,x)≥W(Ck n,x)for all x ∈Rwith 0≤x≤1. Theorem 12. If Gn,dis the graph described in Definition 4, for every connected graph G of order n and diameter d we have W(G,x)≥W(Gn,d,x)for all x ∈Rwith x ≥1, W(G,x)≤W(Gn,d,x)for all x ∈Rwith 0≤x≤1. Theorem 13. Let G be a connected graph of order n and size at least m, and let G′be a connected graph of order n, size m, and diameter at most two. Then W(G,x)≥W(G′,x)for all x ∈Rwith x ≥1, W(G,x)≤W(G′,x)for all x ∈Rwith 0≤x≤1. Theorem 14 (a).Let G be a tree of order n. Then W(G,x)≥W(K1,n−1,x)for all x ∈Rwith x ≥1, W(G,x)≤W(K1,n−1,x)for all x ∈Rwith 0≤x≤1. (b) Let G be a connected planar graph of order n. Then W(G,x)≥W(K2+Pn−2,x)for all x ∈Rwith x ≥1, W(G,x)≤W(K2+Pn−2,x)for all x ∈Rwith 0≤x≤1. (c) Let G be a connected outerplanar graph of order n. Then W(G,x)≥W(K1+Pn−1,x)for all x ∈Rwith x ≥1, W(G,x)≤W(K1+Pn−1,x)for all x ∈Rwith 0≤x≤1. (d) Let G be a connected graph of order n with no complete subgraph of order k. Then W(G,x)≥W(Tn,k,x)for all x ∈Rwith x ≥1, W(G,x)≤W(Tn,k,x)for all x ∈Rwith 0≤x≤1. We note that essentially the same proof yields similar statements for the kth derivative of the Hosoya polynomial and all x∈Rwith x≥1. R.M. Casablanca and P. Dankelmann / Discrete Applied Mathematics 263 (2019) 105–117 113 6. On eccentric sequences of graphs In this section we consider eccentric sequences of graphs, introduced by Lesniak [21] and our aim is to prove results on the eccentric sequence similar to those in Section 3on the distance sequence. Recall that the eccentricity of a vertex vin a connected graph Gis defined as the distance from vto a vertex farthest from v. Definition 5. Let Gbe a connected graph of order n. The eccentric sequence E(G) is the non-increasing sequence (e1,e2,...,en) of the eccentricities of the vertices of G. If A⊆V(G) is a set of vertices of G, then E(G)|Ais the non-increasing sequence of the eccentricities in Gof the vertices in A. Lesniak [21] characterised sequences that are eccentric sequences of trees. The problem of finding a characterisation of eccentric sequences of graphs seems hard, and a solution remains elusive. To date, the only graph class other than trees for which a characterisation of their eccentric sequences is known are maximal outerplanar graphs (see [5]). The following result shows that eccentric sequence of any connected graph is dominated by the eccentric sequence of a path, when both graphs have the same order. Lemma 7. Let G be a connected graph of order n. Then E(G)≤E(Pn). Proof. Let (e1,e2,...,en) be the eccentric sequence of a connected graph Gof order n. We show that ei≤n−⌈i 2⌉for i=1,2,...,n.(8) Let Tbe a spanning tree of G. It suffices to prove (8) for T since the eccentricity of a vertex in a spanning tree of Gis not less than its eccentricity in G. The proof is by induction on n. Inequality (8) clearly holds for n=2 and n=3. Now let n≥4. Let uand vbe two vertices of Tat distance diam(T), and let T′=T−{u, v}. Since uand vare end-vertices of T, the graph T′is connected and thus a tree. Let e∗ 1,e∗ 2,...,e∗ n−2be the eccentric sequence of T′. By our induction hypothesis we have e∗ i≤n−2−⌈i 2⌉for i=1,2,...,n−2. The eccentricity of uand vis at most n−1, and removing uand vhas reduced the eccentricities of the remaining vertices of Tby at most one. Hence e1≤n−1,e2≤n−1 and ei≤e∗ i−2+1≤n−2−⌈i−2 2⌉+1=n−⌈i 2⌉, for i=1,...,n, which implies (8). It is easy to verify that if G=Pn, then we have equality in (8) for all i. Hence the lemma follows. □ Lemma 8. Let G be a 2k-connected graph of order n, where k ∈N. Then E(G)≤E(Ck n). Proof. Since Gis 2k-connected, the eccentricity of any vertex cannot exceed ⌈n−1 2k⌉. Hence E(G)≤(⌈n−1 2k⌉,⌈n−1 2k⌉,...,⌈n−1 2k⌉). It is easy to verify that E(Ck n)=(⌈n−1 2k⌉,⌈n−1 2k⌉,...,⌈n−1 2k⌉). Hence the Lemma follows. □ We now consider graphs of given order and minimum degree δ. Below we define a graph Gn,δ whose eccentric sequence ‘almost dominates’ that of every connected graph of order nand minimum degree δ. More precisely, we show that no term in the eccentric sequence of a graph of order nand minimum degree δexceeds the corresponding term in E(Gn,δ) by more than 3. Example 1. Consider the graph Pℓ,δ, obtained from a path P3ℓ:v0, v1, . . . , v3ℓ−1by adding sets Viof δ−2 new vertices which form a clique and are adjacent to vi−1, viand vi+1for i=1,4,7,...,3ℓ−2. Fig. 1 shows P5,4.