# A Note on the Minimum Wiener Polarity Index of Trees with a Given Number of Vertices and Segments or Branching Vertices

Authors: Sadia Noureen; Akhlaq Ahmad Bhatti; Akbar Ali
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

The Wiener polarity index of a graphG, usually denoted by WpG, is defined as the number of unordered pairs of those vertices of G that are at distance 3. A vertex of a tree with degree at least 3 is called a branching vertex. A segment of a tree T is a nontrivial path S whose end-vertices have degrees different from 2 in T and every other vertex (if exists) of S has degree 2 in T. In this note, the best possible sharp lower bounds on the Wiener polarity index Wp are derived for the trees of fixed order and with a given number of branching vertices or segments, and all the trees attaining this lower bound are characterized.


---

## Body

## 1. Introduction

A topological index is a numerical quantity calculated from a graph, which remains unchanged under graph isomorphism [1]. Topological indices have attracted much attention in recent years, as many of them provide a good correlation between the molecular structure of a chemical compound and its properties. Examples for calculating the topological indices of particular graphs can be found in [2–4].The Wiener polarity indexWp is one of the oldest topological indices, which was proposed in 1947 by the chemist Harold Wiener [5], for predicting the boiling points of paraffins. The index Wp for a graph G is defined as the number of unordered pairs of those vertices of G that are at distance 3. In the previous decade, Wp has attracted much attention from researchers; for example, see the surveys [6, 7], papers [8–25], and related references therein.Before moving further, let us recall some definitions and notations first. All the graphs considered in this note are simple and finite. LetG be a graph with the vertex set VG and the set of edges EG. The degree of a vertex u∈VG is denoted by duG (or simply by du if the graph under consideration is clear). The number of vertices in a graph is known as its order. A graph of order n is called an n-vertex graph. A vertex of degree 1 is called pendent vertex, while a vertex of degree greater than 2 is known as a branching vertex. Let NGu (or Nu) be the set of all those vertices of G that are adjacent to the vertex u∈VG. As usual, we denote by Pn and Sn the path and the star graph of order n, respectively. A segmentS of a tree T is a nontrivial path (that is, a path of length at least 1) in T with the property that both the end-vertices of S have degrees different from 2 in T and every other vertex (if exists) of S has degree 2. A tree ST is called starlike tree (or generalized star) if it contains exactly one branching vertex (we call it the central vertex of ST). A path P=v0,v1,…,vk in a tree T is called a pendent path (internal path, respectively) of length k, if one of the two vertices v0, vk is pendent and the other is branching (both the vertices v0 and vk are branching, respectively) and dvi=2 if 1≤i≤k−1. The notation and terminology of (chemical) graph theory that are not defined in this note can be found in [1, 26–28].By using the definition of the Wiener polarity index, Lukovits and Linert [29] demonstrated the quantitative structure-property relationships in a series of acyclic and cycle-containing hydrocarbons. Considerable work has been done, however, on characterizing the trees that maximize or minimize Wp under various additional conditions: for example, with given order [15], degree sequence [30, 31], diameter [32], and pendent vertices [33, 34]. Shafique and Ali [35] gave some structural properties of the trees of fixed order and with a given number of segments or branching vertices having maximum/minimum Wp value. Here, in this note, we are specifically interested in extending the results obtained in the paper [35].Du et al. [15] showed that Wp of a tree T can be written as(1)WpT=∑uv∈ETdu−1dv−1,where uv is the edge connecting the vertices u,v∈VT. Here, it is important to note that Wp coincides with reduced second Zagreb index [35–37], for the case of trees.For fixed integersn and s, denote by STn,s and Tn,b the classes of all n-vertex trees with s segments and b branching vertices, respectively, where 1≤s≤n−1 and 1≤b≤n/2−1. In this note, we characterize all the trees attaining minimum Wp value from each of the two classes STn,s and Tn,b and hence provide the solution of a problem, left open in [35], concerning the minimum Wp value.LetT′ be a tree obtained from a tree T after applying a transformation such that VT=VT′. Throughout this note, whenever we consider such trees, by dv and Nv we mean the degree and set of neighbors, respectively, of the vertex v∈VT=VT′ in T.


## 2. Sharp Lower Bound on Wiener Polarity Index forn-Vertex Trees with a Fixed Number of Segments

Note thatSTn,1 consists of only the path graph Pn, and STn,2 is empty. Thus, we proceed in this note with the assumption 3≤s≤n−1. Denote by Ssn∈STn,s the starlike tree with s−1 pendent paths of length 1 (see Figure 1). Let STn,s∗⊂STn,s be the class of all n-vertex trees with exactly one internal path and s−1 pendent paths of length 1. For the tree(s) having the minimum Wiener Polarity index among all the members of the class STn,s, we firstly prove some lemmas.Figure 1
The graphSsn.Lemma 1.
Letn and s be positive integers such that 3≤s≤n−1. If T∈STn,s is a tree such that WpT is minimum among all the trees of STn,s, then T contains at most one pendent path of length greater than 1.Proof.
Suppose, contrarily, thatP=v0,v1,…,vs and P′=v0′,v1′,…,vl′l,s≥2 are two pendent paths in T, where dv0=dv0′=1 and dvs,dvl′≥3 (note that the vertices vl′ and vs may coincide). If T′=T−vs−1vs−2+vs−2v0′, then T′∈STn,s, and we have(2)WpT−WpT′=dvs−2>0,a contradiction to the choice of T.
Lemma1 ensures that the trees S3n and S4n have the minimum Wp value in the classes STn,3 and STn,4, respectively. Also, it is obvious that the star graph Sn gives the minimum Wp value (that is, 0) in the class STn,n−1. Therefore, we proceed with the assumption 5≤s≤n−2. Denote by STs⊂STn,s the subclass consisting of all starlike trees. Moreover, by Lemma 1, Ssn attains the minimum Wp value in the class STs. Now, we consider the class STn,s∖STs where 5≤s≤n−2.Lemma 2.
Letn and s be positive integers such that 5≤s≤n−2. If T∈STn,s∖STs is a tree having minimum Wp value among all the members of STn,s∖STs, then each pendent path of T is of length 1.Proof.
We contrarily assume that there is a pendent pathP:=v0,v1,…,vs of length s≥2 in T, where dv0=1 and dvs≥3. Let v∈VT be a branching vertex different from vs and let u be the neighbor of vs lying on the vs - v path. Note that du≥2 and that u may coincide with v. Let T′=T−vsu,v0v1+v0vs,v1u, it can be observed that T′∈STn,s∖STs, and we have WpT−WpT′=du−1dvs−2>0, a contradiction to the choice of T.Theorem 1.
Letn and s be positive integers such that 3≤s≤n−2. If T∈STn,s, then(3)WpT≥n−3,and the equality sign in (3) holds if and only if either T≅Ssn (see Figure 1) or T∈STn,s∗.Proof.
IfT∈STn,s contains more than one pendent path of length at least 2, then by the proof of Lemma 1, there exists a tree T∗ having at most one pendent path of length at least 2 such that WpT>WpT∗. Thus, it is enough to prove the result when T∈STn,s contains at most one pendent path of length at least 2. In the remaining proof, we assume that T∈STn,s has at most one pendent path of length at least 2.
If eitherT≅Ssn or T∈STn,s∗, then by elementary calculations, one has WpT=n−3. We apply induction on s to prove the desired result. Note that if s=3 or 4, then by Lemma 1, it holds that WpT≥n−3 with equality if and only if T≅Ssn. Also, if s=5, then by using Lemmas 1 and 2, we have WpT≥n−3 with equality if and only if either T≅S5n or T∈STn,5∗. Next, suppose that 6≤s≤n−2 and that the result holds for every s′ satisfying 3≤s′≤s−1.
LetP:w1,w2,…,wr be a longest path in T, where r≥4. Note that each of the two vertices w2 and wr−1 has exactly one nonpendent neighbor in T. Since T contains at most one pendent path of length at least 2, at least one of the two vertices w2 and wr−1 is branching. Without loss of generality, we assume that w2 is branching. Let Nw2=w1,w3,u1,u2,…,ut where t≥1 and dui=1 for every i∈1,2,…,t. Let T′=T−u1. Note that T′∈STn−1,s−1 when t≥2, and T′∈STn−1,s−2 when t=1. Hence, by using the inductive hypothesis, we have(4)WpT=WpT′+dw3−1≥n−4+dw3−1≥n−3.
Ift≥2, then the equality WpT=n−3 holds if and only if dw3=2 and either T′∈STn−1,s−1∗ or T′≅Ss−1n−1. If t=1, then the equality WpT=n−3 holds if and only if dw3=2 and T′≅Ss−2n−1 (because in this case, the tree T′ contains a pendent path of length at least 2). Thus, we conclude that WpT≥n−3 with equality if and only if T≅Ssn or T∈STn,s∗. This completes the induction and hence the proof.


## 3. Sharp Lower Bound on Wiener Polarity Index forn-Vertex Trees with a Given Number of Branching Vertices

Recall thatTn,b is the class of all n-vertex trees with b branching vertices, where 1≤b≤n/2−1. For b=1, the star graph Sn attains the minimum Wp value (see [36]). Thus, throughout this section, we assume 2≤b≤n/2−1. Note that Lemma 3 may be proved in a fully analogous way to that of Lemma 2.Lemma 3 (see [35]).
Letb and n be positive integers such that 2≤b≤n/2−1. If T∈Tn,b is a tree having minimum Wp value among all the members of Tn,b, then every pendent path of T is of length 1.
Letxi,j be the number of edges in a tree T connecting the vertices of degrees i and j.Lemma 4.
Letb and n be positive integers such that 2≤b≤n/2−1. If T∈Tn,b is a tree having minimum Wp value among all the members of Tn,b and xi,1≠0 for some i≥4, then T does not contain any pair of adjacent branching vertices.Proof.
Contrarily, suppose thatw,z∈VT is a pair of adjacent branching vertices and let v∈VT be a pendent vertex adjacent to a vertex u∈VT of degree at least 4. Note that u may coincide with either of the vertices w and z. If T′=T−vu,wz+wv,vz, then it can be observed that T′∈Tn,b, and we have(5)WpT−WpT′=∑x∈Nu,x≠vdx−1+dwdz−2dw−2dz+3,which is positive because of the fact that the function fa,b=ab−2a−2b+3 is strictly increasing in both a and b where a,b∈3,∞. Thus, we arrived at a contradiction to the choice of T.Lemma 5.
Letb and n be positive integers such that 2≤b≤n/2−1. If T∈Tn,b is a tree with minimum Wp among the trees from Tn,b, such that uv∈ET with du=1 and dv≥4, then a tree T′∈Tn,b can be obtained from T as T′=T−vw+uw, where w is a nonpendent neighbor of v, such that WpT≥WpT′.Proof.
It holds, as it is easy to see thatT′∈Tn,b. Also, using the facts dw≥2 and dv≥4, we have(6)WpT−WpT′=dv−1dw−1+dv−1∑z∈Nv,z≠u,z≠wdz−1−dw−1−dv−2−dv−2∑z∈Nv,z≠u,z≠wdz−1=dvdw−2dv−2dw+4+∑z∈Nv,z≠u,z≠wdz−1≥0,which implies WpT≥WpT′.Lemma 6.
Letb and n be positive integers such that 2≤b≤n/2−1. If T∈Tn,b is a tree having minimum Wp value among all the members of Tn,b, then every vertex of degree greater than 3 in T has exactly one nonpendent neighbor.Proof.
We contrarily assume that the vertexu∈VT, with Nu=u1,u2,…,uq,uq+1,…,ut, has at least two nonpendent neighbors where t≥4. We consider the following cases:Case 1.
The vertexu has at least one pendent neighbor.
Without loss of generality, we assume thatdui=1 for 1≤i≤q and duj=dj≥2 for q+1≤j≤t. Then, t−q≥2 because u has at least two nonpendent neighbors. Lemma 4 ensures that dj=2 for every j satisfying q+1≤j≤t. If T′=T−uut+utu1, then T′∈Tn,b and hence, because of the fact t−q≥2, we have(7)WpT−WpT′=t−q−1>0,which is a contradiction.Case 2.
The vertexu has nonpendent neighbor.
In this case, we havedui≥2 for every i satisfying 1≤i≤t. Here, Lemmas 3–5 ensure that there is a pendent vertex v∈VT having the neighbor w such that dw=3 for dui≥2, where 1≤i≤t. Let u1 be the neighbor of u that lies on the unique v - u path. If T′=T−uut+vut, then T′∈Tn,b, and we have(8)WpT−WpT′=∑x∈Nu,x≠utdx−1+du−2dut−1−2>0,which is again a contradiction to the choice of T.Theorem 2.
Letb and n be positive integers such that 2≤b≤n/2−1. If T∈Tn,b, then(9)WPT≥n+b−5,2≤b<n−13,4b−4,n−13≤b≤n2−1,and the equality holds if and only if T∈T1∗, for 2≤b<n−1/3, where T1∗=T: T is a tree whose every vertex with degree ≥4 has exactly one nonpendent neighbor and each internal path is of length at least 2}, and T∈T2∗, for n−1/3≤b≤n/2−1, where T2∗ is a class of trees with degree sequence 3,3,…,3︸b,2,2,…,2︸n−2b−2,1,1,…,1︸b+2 such that each pendent vertex of T∈T2∗ is adjacent to some branching vertex only.Proof.
Denote byNi the number of vertices of degree i in a graph G. Let T be a tree that minimizes Wp among the class Tn,b. Lemma 3 and Lemma 4 conclude that whenever n−1/3≤b≤n/2−1, every branching vertex in T has degree 3 such that the vertices of degree 2 are placed between the adjacent vertices of degree 3 in such a way that no two vertices of degree 2 are adjacent if there are adjacent vertices of degree 3. Note that, for n−1/3≤b≤n/2−1, we have N3=b, N1=b+2 and N2=n−2b−2. Hence, WpT=4b−4.
Now, Lemmas3–6 conclude that every internal path has a length of at least 2. Also, Lemma 5 ensures that, to obtain minimal graph T, either we have to insert the vertices of degree 2 between any vertex of degree 2 and vertex of degree 3, or we have to add a starlike pendent vertex in such a way that every vertex with degree ≥4 has exactly one nonpendent neighbor that is T≅T1∗. Hence, WpT=n+b−5, for 2≤b<n−1/3, which completes the proof.



---

*Source: 1052927-2021-01-23.xml*