# On the Wiener Indices of Trees Ordering by Diameter-Growing Transformation Relative to the Pendent Edges

Authors: Xiaoxin Xu; Yubin Gao; Yanbin Sang; Yueliang Liang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

The Wiener index of a graph is defined as the sum of distances between all unordered pairs of its vertices. We found that finite steps of diameter-growing transformation relative to vertices can not always enable the Wiener index of a tree to increase sharply. In this paper, we provide a graph transformation named diameter-growing transformation relative to pendent edges, which increases Wiener indexW(T) of a tree sharply after finite steps. Then, twenty-two trees are ordered by their Wiener indices, and these trees are proved to be the first twenty-two trees with the first up to sixteenth smallest Wiener indices.


---

## Body

## 1. Introduction

Graph theory has been applied in many areas of engineering extensively, such as mechanical design and manufacturing and chemical engineering. The link in the mechanism can be regarded as the vertex in the graph theory, kinematic pair can be regarded as an edge, and then the topological configuration of the mechanism is abstracted as the graph in graph theory. Therefore, relevant theories of graph theory can be used to analyse and discuss the nature and characteristics of the mechanism and especially be used to explore the movement patterns of the mechanism. Analogously in chemical engineering, a chemical molecule is usually regarded as a two-dimensional graph, and the graph’s vertices represent atoms and edges represent chemical bonds. Thus, the graph determines the topological properties of the given molecule. In fact, chemists are often interested in the Wiener indices of certain trees which represent certain molecular structures. In this paper, we study the trees with the first up to sixteenth smallest Wiener indices.All graphs considered in this paper are simple and connected. LetG be a graph that vertex set is V(G) and edge set is E(G). For any u,v∈V(G), the distance dG(u,v) between u and v in G is the length of a shortest u-v path. As the oldest graph-based structure descriptor (topological index), Wiener index was first provided by Wiener in [1] and defined as (1)WG=∑u,v⊆VGdGu,v.Its mathematical properties and chemical applications have been extensively studied in many literatures. In [1], Wiener provided an alternative calculating form of Wiener index for each tree T; i.e., (2)WG=∑e=uv∈ETnTuenTve,where nTu(e)(resp., nTv(e)) is the number of vertices of the component of T-e containing u(resp., v). It should be mentioned that the above equation is valid only for trees.There have been many related achievements on Wiener index and they can be roughly divided into the following categories.(i) Basic Theory and Calculation of Wiener Index (See [2–4]). Many known results about Wiener index of trees were introduced in [2], including the calculation of Wiener index, combinatorial expressions for Wiener index, and the relationship between Wiener index and some characteristic indicators of graph. Manuel et al. in [3] presented a method for calculating Wiener index of certain chemical graphs without using distance matrix. Graovac et al. provided a modification of Wiener index which considers the symmetry of a graph in [4].(ii) The Wiener Index for Several Types of Trees (See [5–7]). Fuchs et al. in [5] studied the Wiener index for several types of random digital trees. Wagner in [6] demonstrated that every integer n (n≥470) is the Wiener index of a star-like tree. [7] derived formulas for calculating the Wiener indices when a tree was modified.(iii) Other Topological Indices Associated with Wiener Index (See [8–16]). The Steiner Wiener index, its inverse problem and the Steiner hyper-Wiener index of a graph were studied in [8–11]. References [12–14] investigated the terminal Wiener index of graphs. For the results about the trees’ reverse Wiener indices and ordering problem by their reverse Wiener indices, one can refer to [15, 16].Since every atom has a certain valency, chemists especially focus on the trees with the maximum (resp., minimum) Wiener index. References [17–22] characterized some n-vertex trees which minimize or maximize the Wiener index over the set of trees with some degree and diameter restrictions.It is natural to consider not only the maximum and minimum Wiener indices of given trees, but also the order of trees by Wiener indices. Ordering trees by their Wiener indices can help us to analyse and evaluate the relationship between the Wiener indices and the structures of chemical molecules represented by the certain trees. Actually, Dong et al. in [23] ordered fifteen trees with 3≤d≤5 in terms of the number of nonpendent edges. The trees with given matching number have been ordered by their Wiener indices in [24].Motivated by the results above, we extend the conclusion in [23] to general case in this paper. In Section 2, we present an example which shows that the result of Lemma 5 in [20] is not always true. As a by-product, we provide diameter-growing transformation relative to pendent edges; this transformation increases Wiener index W(T) sharply after finite steps. Then, we amend the proof of Theorem 2 in [20] by applying this transformation. In Section 3, we order twenty-two trees by their Wiener indices and prove that these trees on n≥28 are the first twenty-two trees with the first to sixteenth smallest Wiener indices.Throughout the paper, we denote the set of trees onn vertices by Tn, and the set of trees on n vertices with diameter d by Tn,d.


## 2. The Trees’ Diameter-Growing Transformation Relative to Pendent Edges

The following example shows the conclusion of Lemma 5 in [20] that W(T′)>W(T) is not always true. In fact, finite steps of diameter-growing transformation of T relative to vertices can not always enable W(T) to increase sharply.Example 1.
For eachn>9, the trees T and T′ are defined as in Figure 1. Then (3)WT>WT′.Figure 1
Diameter-growing transformation ofT relative to the vertex v.Proof.
From equality (2), it follows that W(T)=n2+3n-22=(n2+2n-13)+(n-9) and W(T′)=n2+2n-13. So, it is obvious that W(T)>W(T′) holds for all n>9.To prove that Theorem 2 in [20] is still true, we firstly show that the Wiener index W(T) increases sharply after finite steps of diameter-growing transformation of trees relative to pendent edges.Lemma 2.
LetT∈Tn,d with the longest path P=v0v1⋯vd-1vd. Suppose T′=T-vi-1vi+vi-1u(1≤i≤d-1). Then W(T′)>W(T). In addition, the procedure from T to T′ shown in Figure 2 is called a diameter-growing transformation of T relative to the pendent edge viu.Figure 2
Diameter-growing transformation ofT relative to the pendent edge viu.Proof.
Lete=viu be the pendent edge of T, e′=viu be the nonpendent edge of T′, and T1 and T2 be the two components of T′-e′ containing u and vi. Then VT1≥2 and VT2≥2. Thus, it follows that (4)WT′-WT=n1e′n2e′-n1en2e=VT1VT2-VT1+VT2-1=VT1-1VT2-1>0.In fact, from the proof of Lemma2, we can get the diameter-growing transformation relative to pendent edges in such general case as follows.Remark 3.
For any treeT defined as in Figure 3 and viu(i≥1) being a pendent edge of T, it follows that W(T)<W(T-vi-1vi+vi-1u).Figure 3
Diameter-growing transformation ofT relative to the pendent edge viu.LetMTn,k be the set of trees of order n with exactly k(≤n-2) vertices of maximum degree and M(n,k) be the tree shown in Figure 4.Figure 4
The treeM(n,k) with x=n-2k-2.Theorem 4 (Theorem 2 in [20]).
LetT∈MTn,k, where 1≤k≤n-3. Then (5)WT≤WMn,kwith equality if and only if T=M(n,k).Actually, the proof of Theorem4 (Theorem 2 in [20]) is just needed to be modified by replacing Lemma 5 in [20] with Lemma 2 in our paper.


## 3. The First Twenty-Two Trees inTn with the First up to Sixteenth Smallest Wiener Indices

In this section, firstly, we give the order of twenty-two trees onn≥28 vertices according to Wiener indices by using the diameter-growing transformation relative to pendent edges.Theorem 5.
For anyn≥24, let Ti, Tjk(k=1,2;i=1,2,3,4,5,7,8,10,12,13;j=6,9,11,14,15,16) be some trees on n vertices listed as in Figure 5, where d is the diameter of each tree. Then we have (6)WT1<WT2<WT3<WT4<WT5<WT61=WT62<WT7<WT8<WT91=WT92<WT10<WT111=WT112<WT12<WT13<WT141=WT142<WT151=WT152<WT161=WT162=WT∗.Figure 5
The treesTi, Tjk, and T∗.Proof.
From equality (2), we can easily get (7)WT1=n-1n-1=n2-2n+1.WT2=n2-n-2=n2-2n+1+n-3.WT3=n2-7=n2-n-2+n-5.WT4=n2-5.WT5=n2+n-14=n2-5+n-9.WT61=WT62=n2+n-10.WT7=n2+n-8.WT8=n2+2n-23=n2+n-8+n-15.WT91=WT92=n2+2n-17.WT10=n2+2n-15.WT111=WT112=n2+2n-13.WT12=n2+2n-11.WT13=n2+3n-34=n2+2n-11+n-23.WT141=WT142=n2+3n-26.WT151=WT152=n2+3n-22.WT161=WT162=n2+3n-20.All the above completes proof of the theorem.For convenience, we denote(8)G=T1,T2,T3,T4,T5,T61,T62,T7,T8,T91,T92,T10,T111,T112,T12,T13,T141,T142,T151,T152,T161,T162.Next, we are going to show thatW(T∗)<W(T) holds for any T∈Tn∖G with n≥28. The proof process is organized according to the diameters of trees.Theorem 6.
For eachn≥28, let T∈Tn,d∖G with d=3. Then (9)WT∗<WT^<WTwhere tree T^ is defined as in Figure 6.Figure 6
The treeT^ with diameter d=3.Proof.
On the one hand, from(10)WT^=7n-7+n-2n-1=n2+4n-47=n2+3n-20+n-27>n2+3n-20=WT∗,we get that W(T∗)<W(T^) for any n≥28. On the other hand, for any T∈Tn,d∖G with d=3 and n≥28, T is just shown as in Figure 7.
It is easy to see thatW(T)-W(T^)=(k+2)(n-k-2)-7(n-7)=(k-5)(n-k-9)>0 holds for any k with 5<k<n-9. Therefore, we get W(T∗)<W(T^)<W(T) for any T∈Tn,d∖G with d=3 and n≥28.Figure 7
The treeT with diameter d=3 and 5<k<n-9.Next, we are going to prove thatW(T∗)<W(T) is always true for each T∈Tn,d∖G with d=4 and n≥18.Lemma 7.
For anyn≥18, d=4, and 2≤i≤j≤n-3, let Si,j be the tree defined as in Figure 8. Then (11)WT∗<WTholds for any T∈{Si,j∣2≤i≤j≤n-3}∖G⊆Tn,d.Figure 8
The treeSi,j with diameter d=4, 2≤i≤j≤n-3.Proof.
For each2≤i≤j≤n-3, we have (12)WSi,j=n2+i+j-4n+3-i2-j2.It follows that (13)Si,j∣i+j=4=T4.Si,j∣i+j=5=T61.Si,j∣i+j=6=T92,T10.Si,j∣i+j=7=T141,T151.Then the proof will be divided into three cases as follows.
Case  1 (i=2). For each 6≤j≤n-6, we have W(S2,j)-W(S2,6)=(j-6)(n-6-j)≥0. Then, from W(S2,6)=n2+4n-37=(n2+3n-20)+(n-17)>W(T∗) for any n≥18, we get (14)WT∗<WS2,6≤WS2,j6≤j≤n-6.Meanwhile, we have S2,n-3=T62, S2,n-4=T91, and S2,n-5=T142.
Case  2 (i=3). For each 5≤j≤n-5, we have W(S3,j)-W(S3,n-5)=(j-5)(n-5-j)≥0. From W(S3,n-5)=n2+4n-31=(n2+3n-20)+(n-11)>W(T∗), it follows that (15)WT∗<WS3,n-5≤WS3,j5≤j≤n-5.Moreover, S3,n-4=T152.
Case  3 (i≥4). For each 4≤i≤j≤n-5, we have W(Si,j)-W(S3,i+j-3)=2(i-3)(j-3)>0, which results in W(Si,j)>W(S3,i+j-3). Together with inequality (15), we get (16)WT∗<WS3,n-5≤WS3,i+j-3<WSi,j8≤i+j≤n-2.Since W(S4,n-5)=n2+5n-38=(n2+3n-20)+2(n-9)>W(T∗), then, for each i≥4 and i+j=n-1, from W(Si,j)-W(S4,n-5)=2(i-4)(n-i-5)≥0, it follows that (17)WT∗<WS4,n-5≤WSi,ji+j=n-1.All the above implies that W(T∗)<W(T) holds for any T∈{Si,j∣2≤i≤j≤n-3}∖G⊆Tn,d.Lemma 8.
For eachn≥18, d=4, 2≤i≤j, and 1≤l≤m≤k≤i≤j≤n-6, let Sl,m,k,i,j be the tree defined as in Figure 9. Then W(T∗)<W(T) holds for any T∈{Sl,m,k,i,j∣2≤i≤j,1≤l≤m≤k≤i≤j≤n-6}∖G⊆Tn,d.Figure 9
The treeSl,m,k,i,j with diameter d=4, i,j≥2, and 1≤l≤m≤k≤i≤j≤n-6.Proof.
The proof will be divided into the following cases.
Case  1 (k=1). Then m=l=1, and S1,1,1,i,j=Si,j for each 2≤i≤j≤n-6. Using Lemma 7, it is obvious that W(T∗)<W(T) holds for any T∈{S1,1,1,i,j∣2≤i≤j≤n-6}∖G.
Case  2 (k>1)
Case  2.1 (m=1). Then l=1. We get (18)WS1,1,k,i,j=n2+i+j+k-5n+4-i2-j2-k2.So, it follows that (19)S1,1,k,i,j∣i+j+k=6=T7,S1,1,k,i,j∣i+j+k=7=T111,S1,1,k,i,j∣i+j+k=8=T162,S1,1,2,3,3.However, W(S1,1,2,3,3)=n2+3n-18>W(T∗).
For any1<k≤i≤j with i+j+k≥9, this case can be divided into two subcases as follows.
Case  2.1.1 (k=2). If i=2, from i+j+k≥9 and i+j+5≤n, it follows that 5≤j≤n-7<n-4, and hence (20)WS1,1,2,2,j-WS1,1,2,2,4=j-4n-j-4>0.Note that S1,1,2,2,4=T162=T∗, so W(T∗)=W(S1,1,2,2,4)<W(S1,1,2,2,j) for each j≥5.
Ifi≥3, then j≥3. So W(S1,1,2,i,j)≥W(S1,1,2,3,3)>W(T∗). In fact, for each j≥i≥3, from i+j+5≤n, we conclude that (21)WS1,1,2,i,j-WS1,1,2,3,3=i-3n-i-3+j-3n-j-3≥0.Thus, we have (22)WT∗<WS1,1,2,3,3≤WTfor any T∈{S1,1,k,i,j∣2≤i≤j≤n-7}∖G.
Case  2.1.2 (k≥3). For each j≥i≥k≥3, from i+j+k+3≤n, we can get W(S1,1,k,i,j)-W(S1,1,2,3,3)=(i-3)(n-i-3)+(j-3)(n-j-3)+(k-2)(n-k-2)>0. Then it follows that W(S1,1,k,i,j)>W(S1,1,2,3,3)>W(T∗).
Case  2.2 (m>1)
Case  2.2.1 (l=1). Since T12=S1,2,2,2,2∈G, for any T∈{Sl,m,k,i,j∣2≤i≤j,1=l<m≤k≤i≤j≤n-6}∖G⊆Tn,d, then T=S1,m,k,i,j for some j≥3. So, we have W(T)=W(S1,m,k,i,j)≥W(S1,2,2,2,3)=n2+3n-16>W(T∗) for j≥3.
Actually, fromj≥i≥k≥m≥2 and i+j+k+m+l+1≤n, we get n-3>j≥i≥k≥m≥2. Combining with j≥3, it follows that (23)WT-WS1,2,2,2,3=WS1,m,k,i,j-WS1,2,2,2,3=i-2n-i-2+j-3n-j-3+k-2n-k-2+m-2n-m-2≥0.
Case  2.2.2 (l≥2). Then we have W(Sl,m,k,i,j)≥W(S2,2,2,2,2)=n2+3n-14>W(T∗). Indeed, from j≥i≥k≥m≥l≥2 and i+j+k+m+l+1≤n, we get that n-2>j≥i≥k≥m≥l≥2, and hence (24)WSl,m,k,i,j-WS2,2,2,2,2=i-2n-i-2+j-2n-j-2+k-2n-k-2+m-2n-m-2+l-2n-l-2≥0.
From all of the above cases, it turns out thatW(T∗)<W(T) holds for any T∈{Sl,m,k,i,j∣2≤i≤j,1≤l≤m≤k≤i≤j≤n-6}∖G⊆Tn,d.Lemma 9.
LetT be a tree on n vertices and T~ be a tree transformed from T just as shown in Figure 10. Then, for each given i(2<i<n), W(T~)<W(T) holds for any k with i<k<n-i. It is equivalent to say that W(T~)<W(T) holds for i<G<n-i, where G is the order of G.Figure 10
The treeT~ transformed from tree T.Proof.
Actually,W(T)-W(T~)=k(n-k)-i(n-i)=(k-i)(n-k-i)>0 for any i<k<n-i. In addition, from n=G+k, it follows that i<k<n-i, if and only if i<G<n-i.Actually, the following theorem is a result concluded from Lemmas7, 8, and 9.Theorem 10.
For eachn≥18, and d=4, let T∈Tn,d∖G. Then (25)WT∗<WT.Proof.
The proof will be divided into four cases as follows.
For each givenT∈Tn,d, let Vb(T)={v∈V(T)∣dT(v)≥3} be the set of all branching vertices of T (where dT(v) is the degree of vertex v in T). From the assumption that n≥18 and d=4, it is obvious that Vb(T)≠∅.
Case  1 (VbT=1). Being from T∈Tn,d∖G, together with Lemmas 8 and 9, we get W(T∗)<W(S2,2,2,2,2)≤W(T).
Case  2 (VbT=2). The assumption that n≥18 and d=4 implies that T has at least two nonpendent vertices. If T has exactly two nonpendent vertices, from Lemmas 7 and 9, together with T∈Tn,d∖G, it follows that W(T∗)<W(S2,6)≤W(T). Otherwise, from Lemmas 8 and 9, together with T∈Tn,d∖G, it follows that W(T∗)=W(S1,1,2,2,4)<W(T).
Case  3 (VbT=3). The assumption that n≥18 and d=4 implies that T has at least two nonpendent vertices. If T has exactly two nonpendent vertices, from Lemmas 7 and 9, together with T∈Tn,d∖G, it follows that W(T∗)<W(S2,6)≤W(T). Otherwise, from Lemmas 8 and 9, it follows that W(T∗)<W(S1,1,2,3,3)≤W(T).
Case  4 (VbT≥4). From Lemmas 8 and 9, we get that W(T∗)<W(S1,1,3,3,3)≤W(T).Theorem10 demonstrated the Wiener indices of the trees with diameter 4. Next, we will study the Wiener indices of the trees with diameters 5≤d≤n-2.It is well-known that [25] obtained the trees with minimum and second-minimum Wiener indices among all the trees with n vertices and diameter d. To be more precise, the authors in [25] pointed out that the tree which attains the minimum Wiener index in Tn,d is Tn,d,d/2 and that the tree which attains the second-minimum Wiener index in Tn,d is Zn,d,d/2,d/2+1. The trees Tn,d,i and Zn,d,i,i+1 are shown as in Figure 11.Figure 11
Two treesTn,d,i and Zn,d,i,i+1.Lemma 11 (Theorem 3.6 in [25]).
LetTn,d be the set of all trees on order n with diameter d.
(i) For anyd with 3≤d≤n-2, the tree which attains the minimum Wiener index in the set Tn,d is Tn,d,d/2.
(ii) Ford being odd and 3≤d≤n-3, the tree which attains the second-minimum Wiener index in the set Tn,d is Zn,d,d/2,d/2+1.
(iii) Ford being even and 3≤d≤n-3, the tree which attains the second-minimum Wiener index in the set Tn,d is Tn,d,d/2-1 or Zn,d,d/2,d/2+1.Lemma 12.
For any3≤d≤n-2, we have (26)WTn,d,d/2<WTn,d+1,d+1/2.Proof.
In fact,Tn,d+1,d+1/2=Tn,d,d/2-vd/2vd/2+1+vd/2+1u holds if d is even. Meanwhile, Tn,d+1,d+1/2=Tn,d,d/2-vd/2vd/2-1+vd/2-1u holds if d is odd. From Remark 3, it follows that (27)WTn,d,d/2<WTn,d,d/2-vd/2vd/2+1+vd/2+1u=WTn,d+1,d+1/2,WTn,d,d/2<WTn,d,d/2-vd/2vd/2-1+vd/2-1u=WTn,d+1,d+1/2.Thus, for any tree Tn,d,d/2 in Figure 12 and any Tn,d+1,d+1/2 in Figures 13 or 14, we get W(Tn,d,d/2)<W(Tn,d+1,d+1/2) for each d with 3≤d≤n-2 whenever d is even or odd.Figure 12
The treeTn,d,d/2.Figure 13
The treeTn,d+1,d+1/2 (diameter-growing transformation of tree Tn,d,d/2 for odd d relative to the pendent edge vd/2u).Figure 14
The treeTn,d+1,d+1/2 (diameter-growing transformation of tree Tn,d,d/2 for even d relative to the pendent edge vd/2u).From Lemmas11 and 12, it is easy to get the following conclusion.Theorem 13.
LetT∈Tn,d∖G with 5≤d≤n-2. Then W(T∗)<W(T).Proof.
Since(28)WZn,5,2,3=2n-2+2n-2+4n-4+n-4n-1=n2+3n-20,WT∗=2n-2+2n-2+4n-4+n-4n-1=n2+3n-20,WTn,6,3=2n-2+2n-2+3n-3+3n-3+n-5n-1=n2+3n-20+n-1,we get W(T∗)=W(Zn,5,2,3)<W(Tn,6,3) for any n>1. From Lemma 12, it follows that (29)WTn,6,3<WTn,7,3<WTn,8,4<⋯<WTn,d,d/2<WTn,d+1,d+1/2<⋯.Moreover, from Lemma 11, we get W(Tn,6,3)≤W(T) for any tree T on n vertices with diameter d≥6. By using Lemma 11 again, we get W(Zn,5,2,3)<W(T) for any tree T on n vertices with diameter d=5, except for Tn,5,2 and Zn,5,2,3. Thus, we conclude that (30)WT∗=WZn,5,2,3<WTholds for any tree T on n vertices with diameter d≥5.Theorem 14.
For eachn≥28, let T∈Tn∖G. Then (31)WT1<WT2<WT3<WT4<WT5<WT61=WT62<WT7<WT8<WT91=WT92<WT10<WT111=WT112<WT12<WT13<WT141=WT142<WT151=WT152<WT161=WT162<WT.Proof.
By combining the previous arguments of Theorems5, 6, 10, and 13, the proof is completed.


## 4. Conclusion

In this paper, we provide a transformation of trees named diameter-growing transformation relative to pendent edges. By using this transformation, we amend the proof of Theorem 2 in [20], then give the order of twenty-two trees by their Wiener indices, and prove that these trees are the first twenty-two trees with the first up to sixteenth smallest Wiener indices.



---

*Source: 8769428-2019-02-06.xml*