# Some Properties on the Harmonic Index of Molecular Trees

Authors: Shaoqiang Liu; Jianxi Li
Journal: ISRN Applied Mathematics
 (2014)

---

## Abstract

The harmonic index of a graphG is defined as the sum of weights 2/d(u)+d(v) of all edges uv of G, where d(u) denotes the degree of the vertex u in G. In this paper, some general properties of the harmonic index for molecular trees are explored. Moreover, the smallest and largest values of harmonic index for molecular trees with given pendent vertices are provided, respectively.


---

## Body

## 1. Introduction

LetG be a simple graph with vertex set V(G) and edge set E(G). Its order is |V(G)|, denoted by n. Let d(v) and N(v) be the degree and the set of neighbors of v∈V(G), respectively. The harmonic index of G is defined in [1] as
(1)H(G)=∑uv∈E(G)‍2d(u)+d(v),
where the summation goes over all edges uv of G. This index was extensively studied recently. For example, Zhong [2, 3] and Zhong and Xu [4] determined the minimum and maximum values of the harmonic index for simple connected graphs, trees, unicyclic graphs, and bicyclic graphs, respectively. Some upper and lower bounds on the harmonic index of a graph were obtained by Ilic [5]. Xu [6] and Deng et al. [7, 8] established some relationship between the harmonic index of a graph and its topological indices, such as Randić index, atom-bond connectivity index, chromatic number, and radius, respectively. Wu et al. [9] determined the graph with minimum harmonic index among all the graphs (or all triangle-free graphs) with minimum degree at least two. More information on the harmonic index of a graph can be found in [10].The general sum-connectivity index ofG was proposed by Du et al. in [11] and defined as
(2)χα(G)=∑uv∈E(G)(d(u)+d(v))α.
Clearly, H(G)=2χ-1(G). Du et al. [11] determined the maximum value and the corresponding extremal trees for the general sum-connectivity indices of trees for α<α0, where α0=-4.3586… is the unique root of the equation (4α-5α)/(5α-6α)=3. However, they did not consider the general sum-connectivity indices with α=-1.A molecular treeT is a tree with maximum degree at most four. It models the skeleton of an acyclic molecule [12]. As far as we know, the mathematical properties of related indices for molecular trees have been studied extensively. For example, Gutman et al. [13, 14] determined the molecular trees with the first maximum, the second maximum, and the third maximum Randić indices, respectively. Du et al. [15] further determined the fourth maximum Randić index for molecular trees. Li et al. [16, 17] obtained the lower and upper bounds for the general Randić index R-1 for molecular trees and determined the molecular tree with minimum general Randić index among molecular trees with given pendant vertices. The graphs with maximum and minimum sum-connectivity indices among molecular trees with given pendant vertices were determined in Xing et al. [18].In this paper, we consider the similar problem of determining the graphs with maximum or minimum harmonic index for molecular trees. Some general properties of the harmonic index for molecular trees are explored. Moreover, the smallest and largest values of harmonic index for molecular trees with given pendent vertices are determined, respectively.


## 2. Properties of the Harmonic Index for Molecular Trees

In this section, some general properties of the harmonic index for molecular trees are explored. Before this, some notations are needed. Letℳ𝒯(n) be the set of molecular trees of order n. For T∈ℳ𝒯(n), denote by ni the number of vertices with degree i for i=1,2,3,4, and denote by xij the number of edges in T that connect vertices of degree i and j, where 1≤i≤j≤4. Obviously, n1 is the number of pendant vertices. Note that x11=0. Then we have
(3)n1+n2+n3+n4=n,n1+2n2+3n3+4n4=2(n-1),x12+x13+x14=n1,x12+2x22+x23+x24=2n2,x13+x23+2x33+x34=3n3,x14+x24+x34+2x44=4n4,(4)H(T)=23x12+12x13+25x14+12x22+25x23+13x24+13x33+27x34+14x44.Moreover, Gutman and Miljković in [14] established the following relations:
(5)x14=2n+23-43x12-109x13-23x22-49x23-13x24-29x33-19x34,x44=n-53+13x12+19x13-13x22-59x23-23x24-79x33-89x34.
Substituting these equations into (4), we have
(6)H(T)=7n20-320+1360x12+112x13+320x22+112x23+130x24+120x33+2105x34.Now, let(7)φ(T)=H(T)-(7n20-320)=1360x12+112x13+320x22+112x23+130x24+120x33+2105x34.
Note that from (3), we have n2=(1/2)x12+x22+(1/2)x23+(1/2)x24 and n3=(1/3)x13 + (1/3)x23+(2/3)x33+(1/3)x34. Then we have the following lemma.Lemma 1.
For anyT∈ℳ𝒯(n), if n2+n3≥3, then φ(T)≥72/420.Proof.
We consider the following two cases.
Case
1  (n2+n3>3). Note that
(8)φ(T)=1360x12+112x13+320x22+112x23+130x24+120x33+2105x34=1360x12+340×(2x22)+124x23+130x24+112x13+124x23+140×(2x33)+2105x34≥2n2×130+3n3×2105≥96420sincen2+n3>3.
Thusφ(T)≥96/420>72/420.
Case
2
(n2+n3=3). If n2=3 and n3=0, then
(9)φ(T)=1360x12+320x22+130x24=1360x12+340×(2x22)+130x24≥6×130=84420>72420sincex12+2x22+x24=6.
Ifn2=2 and n3=1, then
(10)φ(T)=1360x12+112x13+320x22+112x23+130x24+120x33+2105x34=1360x12+340×(2x22)+124x23+130x24+112x13+124x23+140×(2x33)+2105x34≥4×130+3×2105=80420>72420,
since x12+2x22+x23+x24=4 and x13+x23+2x33+x34=3.
Ifn2=1 and n3=2, then
(11)φ(T)=1360x12+112x13+320x22+112x23+130x24+120x33+2105x34=1360x12+340×(2x22)+124x23+130x24+112x13+124x23+140×(2x33)+2105x34≥2×130+6×2105=76420>72420,
since x12+2x22+x23+x24=2 and x13+x23+2x33+x34=6.
Ifn2=0 and n3=3, then
(12)φ(T)=112x13+120x33+2105x34=112x13+140×(2x33)+2105x34≥9×2105=72420,sincex13+2x33+x34=9.
This completes the proof.Lemma 2.
For anyT∈ℳ𝒯(n), if n2+n3≤2, then φ(T)<72/420.Proof.
Ifn2+n3≤2, then the graphically feasible combinations of x12,x13,x22, x23,x24,x33, and x34 for which φ(T)<72/420 are listed in Table 1, where n≡k(mod3) and corresponding nine classes of molecular trees are denoted by ℳi𝒯(n) for i=1,2,…,9, respectively.Table 1
Nine classes of molecular trees andφ(T)<72/420.
Set
n
2
n
3
Nonzeroxij′s value
φ
(
T
)
k
n
ℳ
1
T
(
n
)
0
0
0
2
n
≥
5
ℳ
2
T
(
n
)
0
1
x
34
=
3
24
/
420
1
n
≥
13
ℳ
3
T
(
n
)
1
0
x
24
=
2
28
/
420
0
n
≥
9
ℳ
4
T
(
n
)
0
2
x
34
=
6
48
/
420
0
n
≥
21
ℳ
5
T
(
n
)
0
1
x
34
=
2
,
x
13
=
1
51
/
420
1
n
≥
10
ℳ
6
T
(
n
)
0
2
x
34
=
4
,
x
33
=
1
53
/
420
0
n
≥
18
ℳ
7
T
(
n
)
1
1
x
24
=
2
,
x
34
=
3
52
/
420
2
n
≥
17
ℳ
8
T
(
n
)
2
0
x
24
=
4
56
/
420
1
n
≥
13
ℳ
9
T
(
n
)
1
1
x
24
=
1
,
x
34
=
2
,
x
23
=
1
65
/
420
2
n
≥
14Note that the smallerφ(T), the smaller H(T). Then by Lemmas 1 and 2, we have the following properties for ℳ𝒯(n).Theorem 3.
Forn≡0(mod3), if T∈ℳ𝒯(n), then(a)
whenn≥9, H(T)≥(7n/20)-(1/12), the equality holds if and only if T∈ℳ3T(n);(b)
whenn≥21 and T∉ℳ3T(n), H(T)≥(7n/20)-(1/28), the equality holds if and only if T∈ℳ4T(n);(c)
whenn≥21 and T∉ℳ3T(n)⋃‍ℳ4T(n), H(T)≥(7n/20)-(1/42), the equality holds if and only if T∈ℳ6T(n).Theorem 4.
Forn≡1(mod3), if T∈ℳ𝒯(n), then(a)
whenn≥13, H(T)≥(7n/20)-(13/140), the equality holds if and only if T∈ℳ2T(n);(b)
whenn≥13 and T∉ℳ2T(n), H(T)≥(7n/20)-(1/35), the equality holds if and only if T∈ℳ5T(n)(when n=10, H(T)=(7n/20)-(1/35), and T∈ℳ5T(n));(c)
whenn≥13 and T∉ℳ2T(n)⋃‍ℳ5T(n), H(T)≥(7n/20)-(1/60), the equality holds if and only if T∈ℳ8T(n).Theorem 5.
Forn≡2(mod3), if T∈ℳ𝒯(n), then(a)
whenn≥5, H(T)≥(7n/20)-(3/20), the equality holds if and only if T∈ℳ1T(n);(b)
whenn≥17 and T∉ℳ1T(n), H(T)≥(7n/20)-(11/420), the equality holds if and only if T∈ℳ7T(n);(c)
whenn≥17 and T∉ℳ1T(n)⋃‍ℳ7T(n), H(T)≥(7n/20)+(1/210), the equality holds if and only if T∈ℳ9T(n).In [5], Ilic deduced that by removing an edge with the minimal weight from a graph, where the weight of e=uv is denoted by 2/(d(v)+d(u)), its harmonic index strictly decreases. For molecular tree T, by removing any pendent vertex from T, we have the following theorem:Theorem 6.
LetT be a molecular tree of order n≥3, and let v be a pendent vertex of  T. Then one has H(T-v)<H(T).Proof.
Lete=uv∈E(T) be a pendent edge, where d(v)=1 and d(u)≥2. Now we consider the difference Δ=H(T)-H(T-v) in the following three cases.
Case
1
(d(u)=2 and N(u)={v1,v}). The result follows from
(13)Δ=2d(v1)+2+23-2d(v1)+1=23-2(2+d(v1))(d(v1)+1)≥23-2(2+1)(1+1)=13.
Case
2
(d(u)=3 and N(u)={v1,v2,v}). The result follows from
(14)Δ=2d(v1)+3+2d(v2)+3+24-2d(v1)+2-2d(v2)+2=12-2(3+d(v1))(d(v1)+2)-2(3+d(v2))(d(v2)+2)≥12-22(3+1)(2+1)=16.
Case
3
(d(u)=4 and N(u)={v1,v2,v3,v}). The result follows from
(15)Δ=2d(v1)+4+2d(v2)+4+2d(v3)+4+25-2d(v1)+3-2d(v2)+3-2d(v3)+3=25-2(3+d(v1))(d(v1)+4)-2(3+d(v2))(d(v2)+4)-2(3+d(v3))(d(v3)+4)≥25-32(3+1)(4+1)=110.
The proof is completed.Remark 7.
Note that removing a pendent vertex is equal to removing an pendent edge. Thus Theorem6 states that, for molecular trees, the removed pendent vertex may not be located at an edge with the minimal weight, which is illustrated by the following example. In Figure 1, the weight of e1 and that of e2 are 2/(d(u)+d(v1))=2/(1+3)=1/2 and 2/(d(v2)+d(v3))=2/(3+3)=1/3, respectively. But H(T-e1)=H(T-u)<H(T).An example ofT-u.
(a)
T, H(T) = 56/15
(b)
T – u, H(T − u) = 52/15


## 3. Smallest Values of Harmonic Index for Molecular Trees with Given Pendent Vertices

In this section, the smallest values of harmonic index for molecular trees with given number of pendent vertices are determined.Theorem 8.
LetT be a tree of order n with p pendant vertices, where 2≤p≤n-2. Then
(16)H(T)≥2p+2-4p+1+n-p2+53,
the equality holds if and only if T≅Sn,p, where Sn,p (shown in Figure 2) is a tree obtained by attaching p-1 pendent vertices to an end vertex of the path Pn-p+1.Figure 2
The treeSn,p.Proof.
Ifp=2, then T≅Pn; the result is obvious. For 3≤p≤n-2, we prove the theorem by induction on n. If n=5, then T≅S5,3 or T≅S5; the result is obvious. Suppose that n≥6. Let u be a pendant vertex and N(u)={v}. Now we consider the d(v) in the following two cases.
Case
1  (d(v)=2). Then T-u contains p pendant vertices. For n≥6, there always exists ω∈N(v)∖{u} such that d(w)≥2. Thus
(17)H(T)-H(T-u)=2d(w)+2+23-2d(w)+1≥24+23-23=12.
The equality holds if and only if d(w)=2.
Ifp=n-2, then T=Sn,n-2; that is, T-u=Sn-1,n-2. Hence d(w)>2; if 3≤p≤n-3 and T-u=Sn-1,p, then d(w)=2. By the induction hypothesis, we have
(18)H(T)≥H(T-u)+12≥2p+2+2(p-1)p+1+23+2(n-p-3)4+12=2p+2-4p+1+n-p2+53.
The equality holds if and only if T-u=Sn-1,p; that is, T≅Sn,p.
Case
2
(d(v)≥3). Then T-u contains p-1 pendant vertices, and N(v)∖{u} contains some vertices with degree at least two. For 3≤p≤n-2, we have
(19)H(T)-H(T-u)=2d(v)+1-∑w∈N(v)∖u‍(2d(w)+d(v)-1-2d(w)+d(v))≥2d(v)+1-(2d(v)-1+2-2d(v)+2)-(d(v)-2)(2d(v)-1+1-2d(v)+1)=2(1d(v)+2-3d(v)+1+2d(v)).
The equality holds if and only if N(v) contains one vertex of degree two and d(v)-1 vertices of degree one. Let g(x)=2((1/(x+2))-(3/(x+1))+(2/x)). Note that g′(x)=-(((4x3+30x2+48x+16)) ⁄ (((x+2)2(x+1)2x2)))<0 for x≥0. Then g(x) is strictly decreasing on x≥0. Recall that d(v)≤p. Hence we have
(20)H(T)-H(T-u)≥2(1p+2-3p+1+2p).
The equality holds if and only if N(v) contains one vertex of degree two and d(v)-1 vertices of degree one; that is, T=Sn,p and d(v)=p. By the induction hypothesis, we have
(21)H(T)≥H(T-u)+2(1p+2-3p+1+2p)≥2p+1-4p+n-p2+53+2(1p+2-3p+1+2p)=2p+2-4p+1+n-p2+53.
The equality holds if and only if T-u≅Sn-1,p-1 and d(v)=p; that is, T≅Sn,p.Lemma 9.
Letn,p be positive integers with 2≤p≤n-2. Let
(22)f(n,p)=2p+2-4p+1+n-p2+53.
Then f(n,p) is monotonically decreasing on p.Proof.
We consider the derivative off(n,p). For p≥2, we have
(23)∂f(n,p)∂p=-2(p+2)2+4(p+1)2-12=-p4-6p3-9p2+12p+242(p+1)2(p+2)2.
Letg(p)=-p4-6p3-9p2+12p+24. Clearly, g(2)<0. We consider the derivative of g(p). For p≥2, we have
(24)g′(p)=-4p3-18p2-18p+12<0.
Thusg(p) is monotonically decreasing on p and g(p)≤g(2)<0. That is, ∂f(n,p)/∂p<0 for 2≤p≤n-2. Hence f(n,p) is monotonically decreasing on p.Recall that ifp=n-1, then Sn,n-1=Sn and H(Sn)=2(n-1)/n. Moreover, by Lemma 9, we have f(n,p)≥f(n,n-2)=(2/n)-(4/(n-1))+1+(5/3)>2(n-1)/n=H(Sn). This together with Theorem 8 implies the followingCorollary 10 (see [5]).
Among all trees of ordern, the minimum harmonic index is attained uniquely by the star Sn.Letℳ𝒯n,p be the set of molecular trees of order n with p pendent vertices. Now we introduce two classes of molecular trees of order n with p pendent vertices.The first class is denoted byℒe(n,p) for even p with 6≤p≤⌊(n+3)/2⌋ (shown in Figure 3). Those trees are composed of (p-2)/2 star S5, which are connected by paths whose lengths may be zero. Note that n1=p,n2=n-(3p/2)+1,n3=0,n4=(p/2)-1,x14=p,x22=n-2p+3, and x24=p-4.Figure 3
An example of molecular tree inℒe(n,p).The second class is denoted byℒl(n,p) for odd p with 9≤p≤⌊(n+2)/2⌋ (shown in Figure 4). Those trees are composed of (p-3)/2 star S5 and one star S4, which are connected by paths whose lengths may be zero, and the unique star S4 is connected by three stars S5. Note that n1=p, n2=n-((3p+1)/2)+1, n3=1, n4=((p-1)/2)-1, x14=p, x24=p-6, x22=n-2p+2, and x23=3.Figure 4
An example of molecular tree inℒl(n,p).Forp≤4, if 3≤n≤5, then Corollary 10 implies that Sn is the unique molecular tree with the minimum harmonic index; if n≥6, then Theorem 8 and Lemma 9 imply that Sn,4 is the unique molecular tree with the minimum harmonic index. If p≥5, then Sn,p is not a molecular tree. The following gives the smallest value for ℳ𝒯n,p with p≥5.Theorem 11.
LetT∈ℳ𝒯n,p and p≥5. Then
(25)H(T)≥n2-415p+16;
the equality holds if and only if T∈ℒe(n,p) for even p with 6≤p≤⌊(n+3)/2⌋. Moreover, if p is odd and 9≤p≤⌊(n+2)/2⌋, then
(26)H(T)≥n2-415p+15;
the equality holds if and only if T∈ℒl(n,p).Proof.
ForT∈ℳ𝒯n,p, Xing et al. [18] deduced the following relations:
(27)x14=p-x12-x13,x22=n-2p-x12-13x13-13x23+13x33+23x34+x44+3,x24=p+x12+13x13-23x23-43x33-53x34-2x44-4.
Substituting these equations into (4), we have
(28)H(T)=n2-415p+16+110x12+245x13+190x23+118x33+463x34+112x44.
Clearly, the minimum value of H(T) is attained at x12=x13=x23=x33=x34=x44=0. That is H(T)≥(n/2)-(4/15)p+(1/6). Moreover if H(T)=(n/2)-(4/15)p+(1/6), then x14=p, x22=n-2p+3, x24=p-4, n2=n-(3p/2)+1, n3=0, and n4=(p/2)-1, implying that T∈ℒe(n,p).
Now suppose that not all ofx12, x13, x23, x33, x34, and x44 in (28) are zero. Let
(29)φ(T)=H(T)-(n2-415p+16)=110x12+245x13+190x23+118x33+463x34+112x44.
Now we consider the following two cases.
Case
1 (x12+x13+x33+x34+x44>0). Then φ(T)≥min{(1/10),(2/45),(1/18),(4/63),(1/12)} = (2/45)>(1/30), the result holds.
Case
2  (x12=x13=x33=x34=x44=0 and x23≠0). Clearly, x23=3n3 since x13+x23+2x33+x34=3n3. Thus the only possible combination of x12, x13, x23, x33, x34, and x44 for which φ(T)≤(1/30) is x12=x13=x33=x34=x44=0, x23=3 with n3=1.
Hence the minimum value ofH(T) is attained at x12=x13=x33=x34=x44=0,x23=3. That is, H(T)≥(n/2)-(4/15)p+(1/5). Moreover if H(T)=(n/2)-(4/15)p+(1/5), then x14=p, x22=n-2p+2, x24=p-6, n2=n-((3p+1)/2)+1, n3=1, and n4=((p-1)/2)-1, implying that T∈ℒl(n,p). This completes the proof.


## 4. Largest Values for Harmonic Index of Molecular Trees with Given Pendent Vertices

In this section, largest values for the harmonic indices of molecular trees with given number of pendent vertices are determined.ForT∈ℳ𝒯n,p, let Vi(T)={v:v∈V(T),d(v)=i} and Ei,j(T)={e:e=uv∈E(T),d(u)=i,d(v)=j}.Letℒ3(n,p) (shown in Figure 5) be a class of molecular trees of order n. For this type of molecular trees, there are p-2 vertices of maximal degree three, which induce a tree and any of these vertices is adjacent to either another vertex of degree three or a vertex of degree two. Note that n1=p, n2=n-2p+2, n3=p-2, n4=0, x12=x23=p, x13=0, x22=n-3p+2, and x33=p-3. Clearly, 3≤p≤⌊(n+2)/3⌋.Figure 5
An example ofL3(n,p).Lemma 12.
LetT be a tree with maximum harmonic index among all trees in ℳ𝒯n,p. Then either E22(T)=∅ or V4(T)⋃‍E13(T)=∅.Proof.
We shall prove the contrapositive of the lemma. IfE22(T)≠∅ and V4(T)∪E13(T)≠∅, then either E22(T)≠∅ and V4(T)≠∅, or E22(T)≠∅ and E13(T)≠∅.
IfE22(T)≠∅ and V4(T)≠∅, then there exists a vertex v∈V4(T) and N(v) has at most one neighbor of degree four. Let T′ be the tree obtained from T by contracting the edge e∈E22(T) and splitting the vertex v into (v1,v2). Clearly, T′∈ℳ𝒯n,p and
(30)H(T′)-H(T)=23+3-22+2+∑w∈N(v)‍(23+d(w)-24+d(w))=-16+∑w∈N(v)‍(23+d(w)-24+d(w))>-16+3(23+3-24+3)+23+4-24+4=184>0;
if E22(T)≠∅ and E13(T)≠∅, suppose that uv∈E13(T), d(u)=1 and d(v)=3. Let T′ be the tree obtained from T by contracting the edge e∈E22(T) and attaching an edge to u. Clearly, T′∈ℳ𝒯n,p and
(31)H(T′)-H(T)=22+1+22+3-22+2-21+3=115>0.
For each case, we have H(T′)>H(T), which contradicts T with maximum harmonic index among all trees in ℳ𝒯n,p. This completes the proof.Theorem 13.
LetT∈ℳ𝒯n,p with p≥2. Then
(32)H(T)≤n2-112p;
the equality holds if and only if T≅Pn.Proof.
For any molecular treeT, the following relations were deduced by Xing et al. in [18]:
(33)x12=p-x13-x14,x22=n-52p+12x13+34x14-12x23-14x24+14x34+12x44+2,x33=32p-12x13-34x14-12x23-34x24-54x34-32x44-3.
Substituting these equations into (4), we have
(34)H(T)=n2-112p-112x13-17120x14-160x23-124x24-1168x34.
Clearly, the maximum value of H(T) is attained at x13=x14=x23=x24=x34=0. That is, H(T)≥(n/2)-(1/12)p. Moreover, if H(T)=(n/2)-(1/12)p, then x12=p, x22=n-(5/2)p+2, x33=(3/2)p-3. Note that x33=x44=0 since T∈ℳ𝒯n,p; that is, p=2,x12=2, and x22=n-3. This implies that T≅Pn.Theorem 14.
LetT∈ℳ𝒯n,p(T≠Pn) with |E23(T)|=p and |E22(T)|≠∅. Then
(35)H(T)≤n2-110p;
the equality holds if and only if T∈ℒ3(n,p).Proof.
From the proof of Theorem13, we can see that if T≠Pn, then not all of x13, x14, x23, x24, and x34 in (34) are zero. By Lemma 12, if T with maximum harmonic index among all trees in ℳ𝒯n,p and E22(T)≠∅, then V4(T)⋃‍E13(T)=∅. That is, x14=x24=x34=x44=x13=0. Theorem 13 implies that x12=p, x22=n-(5/2)p-(1/2)x23+2, and x33=(3/2)p-(1/2)x23-3. If |E23(T)|=p, then x23=p, x12=p, x22=n-3p+2, and x33=p-3. Note that p≥3 and |E23(T)|=p since T≠Pn. Then H(T)≤(2p/3)+(2p/(2+3))+((2(p-3))/(3+3))+((2(n-3p+2))/(2+2))=(n/2)-(1/10)p; the equality holds if and only if T∈ℒ3(n,p). This completes the proof.



---

*Source: 781648-2014-01-29.xml*