# On Harmonic Index and Diameter of Quasi-Tree Graphs

Authors: A. Abdolghafourian; Mohammad A. Iranmanesh
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The harmonic index of a graphG (HG) is defined as the sum of the weights 2/du+dv for all edges uv of G, where du is the degree of a vertex u in G. In this paper, we show that HG≥DG+5/3−n/2 and HG≥1/2+2/3n−2DG, where G is a quasi-tree graph of order n and diameter DG. Indeed, we show that both lower bounds are tight and identify all quasi-tree graphs reaching these two lower bounds.


---

## Body

## 1. Introduction

LetG be a simple connected graph with vertex set VG and edge set EG of order n (VG=n). The harmonic index of G, first appeared in [1], is defined as HG=∑uv∈EG2/du+dv, where for v∈VG, dv is the degree of v in G. For u,v∈VG, the distance between u and v is shown by du,v. Also, DG=maxdu,vu,v∈VG is the diameter of G and δG=mindvv∈VG.The applications of the harmonic index in various chemical disciplines have been demonstrated in [2–4]. Also, several studies have focused on graph theoretical properties of the harmonic index, see, for example, [5–9]. For a broad overview, we refer to [10].A connected graphG is a quasi-tree graph if G is not a tree and there exists a vertex v∈VG such that G−v is a tree. A graph G is called unicyclic if it contains only one cycle. Obviously, every unicyclic graph is a quasi-tree graph. Many researchers have studied topological indices of quasi-tree graphs. See, for example, [11–16].Liu [17] found a relation between harmonic index and diameter of a graph. He proved that if n≥4 and G is a connected graph of order n, then HG≤DG+n/2−1 and HG≤n/2DG. Also, a lower bound was found for trees. If T is a tree of order n≥4, then HT≥DT+5/6−n/2 and HT≥1/2+1/3n−1DT. Thereby, Liu [17] proposed the following conjecture.Conjecture 1.
LetG be a connected graph with order n≥4; then,(1)HG≥DG+56−n2,HG≥12+13n−1DG.Jerline and Michaelraj [18, 19] found a sharper bound for unicyclic graphs. They showed that if G is a unicyclic graph of order n, then HG≥DG+5/3−n/2 and HG≥1/2+2/3n−2DG. They introduced a family of graphs, Un,41,n−5, which is a set of graphs obtained from C4 by attaching one pendant vertex and a path of length n−5 to two diametrically nonadjacent vertices of C4 (see Figure 1). Then, they proposed the following conjecture [18].Figure 1
The graphsUn,41,n−5 and Vr,s.Conjecture 2.
LetG be a simple connected graph, which is not a tree, of order n≥7. Then,(2)HG≥DG+53−n2,HG≥12+23n−2DG,where equality holds if and only if G=Un,41,n−5.They also show that the inequalities of the above conjecture are not true for a graph of order 6, namely,U6,41,1.SupposeK4− is a graph of order 4 which is obtained from K4 by deleting an edge. Also, for r,s≥0, let Vr,s be a family of graphs obtained from K4− by attaching two paths of lengths r and s to two nonadjacent vertices of K4− (see Figure 1). We will show that the inequality holds for all quasi-tree graphs except U6,41,1 and the graph U5,31,1 which is obtained by attaching two pendant vertices to two vertices of K3. Also, the equality holds for V1,1.Two main theorems of this paper are as follows.Theorem 1.
LetG≠U6,41,1,U5,31,1 be a quasi-tree graph of order n≥3. Then, HG≥DG+5/3−n/2. The equality holds if and only if G=V1,1 or Un,41,n−5.Theorem 2.
LetG be a quasi-tree graph of order n≥3 and G≠U6,41,1,U5,31,1. Then, HG≥1/2+2/3n−2DG. The equality holds if and only if G=V1,1 or Un,41,n−5.In Section2, we prove the lemmas that will be used in Section 3, where we prove the main theorems.All graphs considered in this paper are finite, undirected, connected, and simple. LetG be a graph and v∈VG and P a path of G; then, by G−v and G−P, we mean the graph obtained from G by deleting the vertex v and the vertices of P, respectively. For all other notation and definitions not given here, the readers are referred to [20].


## 2. Preliminaries

Lemma 1.
Forx,y≥2, the two variables’ function(3)fx,y=x+4xx+12+x+y+4yy+12+y−2x+yx+y−2,is positive.Proof.
(4)fx,y=x+4xx+12+x+y+4yy+12+y−2x+yx+y−2=2xx+1+−1x+2x+1+2yy+1+−1y+2y+1−2x+yx+y−2=1xx+1−1x+2x+1+1yy+1−1y+2y+1+1xx+1−1x+yx+y−2+1yy+1−1x+yx+y−2.
Givenx,y≥2, the terms inside parentheses are positive.Lemma 2.
x/x+2≥1/5+x+x−1/2+x≥11/28 for every x≥2.Proof.
The first inequality is valid sincex/x+2=1/x+2+x−1/x+2≥1/5+x+x−1/2+x.
Letfx=1/5+x+x−1/2+x. Then, f′x=−1/5+x2+3/2+x2>0. So, f is an increasing function and fx≥f2=11/28 for every x≥2.


## 3. Proof of the Main Theorems

In this section, we will show that Conjecture2 is true for all quasi-tree graphs. Also, in our proof, it will be shown that the equality in both inequalities hold whenever G is the graph V1,1.Lemma 3.
LetG be a quasi-tree graph of order n, where 3≤n≤6, such that G≠U6,41,1,U5,31,1. Then,(5)HG≥DG+53−n2,HG≥12+23n−2DG.Proof.
Ifn=3, then G should be the complete graph, K3. In this case, DG=1 and, by an easy calculation, HG=3/2 and both inequalities hold.
Ifn=4, then, since K4 is not a quasi-tree graph, DG>1. Also, since G is not a tree, G≠P4 and DG=2. Hence, DG+5/3−n/2=1/2+2/3n−2DG=5/3. So, both inequalities hold for n=4 (see Figure 2).
Supposen=5 and w is the vertex that G−w is a tree. Since G−w is a tree of order 4, DG−w=3 or 2. Also, since G is a quasi-tree graph, it is not a complete graph, and hence, DG=3 or 2.
IfDG=3, then DG+5/3−n/2=1/2+2/3n−2DG=13/6. If DG=2, then DG+5/3−n/2=7/6 and 1/2+2/3n−2DG=13/9. All quasi-tree graphs of order 5 and their harmonic indices are shown in Figure 3. As it is seen, all graphs hold both inequalities except when G=U5,31,1.
Supposen=6 and w is the vertex that G−w is a tree. So, G−w is one of P5,K1,4, or K1,3+, where K1,3+ is obtained by attaching a new pendant vertex to a pendant vertex of K1,3.
IfG−w=K1,4, then DG−w=2. Since DG≤DG−w and G is not K6, so DG=2, DG+5/3−n/2=2/3, and 1/2+2/3n−2DG=4/3. On the contrary, for every edge uv of G−w, 2/du+dv is at least 2/7, where du and dv are the degree of u and v in G, respectively. So,(6)HG≥427+∑x∈Nw2dx+dw≥87+25+dw+2dw−12+dw≥87+1114>43.
The second and third inequalities hold by Lemma2.
IfG−w=P5, then the graph G is one of the graphs shown in Figure 4 in which their harmonic indices are calculated. Also, DG≤4, so DG+5/3−n/2≤2+2/3 and 1/2+2/3n−2DG≤2+2/3. So, for every graph both inequalities hold, except when G=U6,41,1. Also, the equality holds when G=V1,1.
IfG−w=K1,3+, then the graph G is one of the graphs shown in Figure 5 in which their harmonic indices are calculated. Also, DG≤3, so DG+5/3−n/2≤1+2/3 and 1/2+2/3n−2DG≤2. Obviously, for every graph, both inequalities hold.Figure 2
Quasi-tree graphs of order 4 and their harmonic indices.Figure 3
Quasi-tree graphs of order 5 and their harmonic indices.Figure 4
Quasi-tree graphs of order 6 obtained fromP5, and their harmonic indices.Figure 5
Quasi-tree graphs of order 6 obtained fromK1,3∗, and their harmonic indices.Theorem 3.
LetG≠U6,41,1,U5,31,1 be a quasi-tree graph with n≥3 vertices. Then, HG≥DG+5/3−n/2. The equality holds if and only if G=V1,1 or G=Un,41,n−5.Proof.
By induction onn, if n≤6, then Theorem 3 implies that the inequality is true, unless when G=U6,41,1,U5,31,1. Also, by Theorem 3, the equality holds when G=V1,1.
LetG be a quasi-tree graph with n≥7 vertices. Suppose w is a vertex of G such that G−w is a tree. Let P=u0−u1−⋯−ud be the diametrical path of G. There are three cases as follows.Case 1. There exists t∈G−P such that dt=1. Since t is not in diametrical path of G and dt=1, DG−t=DG and G−t is a quasi-tree graph too. Suppose Nt=r and G−t≠U6,41,1. Then, by induction hypothesis,(7)HG=HG−t+2dr+1−∑x∈Nrx≠t2dr+dx−1+∑x∈Nrx≠t2dr+dx=HG−t+2dr+1−∑x∈Nrx≠t2dr+dx−1dr+dx≥HG−t+2dr+1−2dr−1drdr+1≥DG+53−n−12+2drdr+1>DG+53−n2.IfG−t=U6,41,1, then G is one of the graphs shown with their harmonic indices in Figure 6. In this case, DG=4 and DG+5/3−n/2=65/30. Hence, the inequality holds.Case 2. Every vertex of G−P is of degree at least 2, and there exists t∈G−P−w such that dt=2. Similar to the previous case, DG=DG−t. Suppose Nt=r,s. Note that dr,ds≥0, otherwise r,s∩P=∅, and hence, t∈P, a contradiction. Since dt=2, it is possible that G−t be a tree. There exist three subcases as follows:Subcase 2.1. G−t is not a tree and rands are not adjacent in G. By the hypothesis, there exist at most two vertices of degree 1 in G which are u0 and ud. If u0,ud∈Nr, then DG=2, and since rands are not adjacent, ds,u0≥3, a contradiction. So, r has at most one neighbor of degree 1. Same argument is valid for s, so(8)HG=HG−t+22+dr+22+ds−2∑x∈Nrx≠t1dr−1+dxdr+dx−2∑y∈Nsy≠t1ds−1+dydy+ds≥DG+53+n−12+22+dr+22+ds−2dr−2dr+1dr+2−2drdr+1−2ds−2ds+1ds+2−2dsds+1=DG+53−n2+12+4dr−1drdr+12+dr+4ds−1dsds+12+ds>DG+53−n2.IfG−t=U6,41,1, then G is one of the graphs which are shown with their harmonic indices in Figure 7. In this case, DG=4 and DG+5/3−n/2=65/30.Subcase 2.2. G−t is not a tree and rands are adjacent in G. If G−t≠U6,41,1, then(9)HG=HG−t+2dr+2+2ds+2+2dr+ds−2dr+ds−2−∑x∈Nrx≠t,y2dx+dr−1dx+dr−∑y∈Nsy≠t,r2dy+ds−1dy+ds≥HG−t+2dr+2+2ds+2−4dr+dsdr+ds−2−2dr−2drdr+1−2ds−2dsds+1≥HG−t−4dr+dsdr+ds−2+2dr+4drdr+1dr+2+2ds+4dsds+1ds+2>DG+53−n2.Sincedr,ds≥2, the last inequality is obtained from Lemma 1.IfG−t=U6,41,1, then G is the graph which is shown with its harmonic index in Figure 8. In Subcase 2.1, DG+5/3−n/2=65/30 and the inequality holds.Subcase 2.3. G−t is a tree. Since G−w is also a tree, by counting the number of edges and vertices, it is obtained that dw=dt=2. This means that G is a unicyclic graph and as proved by Theorem 3 in[19], HG≥DG+5/3−n/2, in which equality holds if G=Un,41,n−5.Case 3. Every vertex of G−u0,u1,…,ud is of degree at least 2 and if t∈VG and dt=2, then t∈u0,u1,…,ud,w. Since G−w is a tree, every pendant vertex of G−w is in u0,u1,…,ud. So, G−w is a path and VG=u0,u1,…,ud∪w. Also, since G is not a tree dw≥2. If dw=2, then G is a unicyclic graph and as proposed by Theorem 3 in [19], HG≥DG+5/3−n/2, with equality holds if G=Un,41,n−5. So, there exist two subcases as follows.Subcase 3.1dw=3. In this case, G is one of the graphs in Table 1. In all cases, HG≥DG+5/3−n/2. As it is shown, the equality holds when G=V1,1.Subcase 3.2 (dw>3). Suppose uh,ui,uj,uk⊆Nw such that h<i<j<k. If k−h>2, then the diametrical path u1−⋯−uh−⋯−uk−⋯−ud is longer than the path u1−⋯−uh−w−uk−⋯,ud, a contradiction. So, k−h≤2, which is another contradiction. Hence, this case does not happen. The inequality holds in all cases and equality holds if and only if G=V1,1 or Un,41,n−5.Figure 6
The graphs related to Case 1 of Theorems3 and 4.Figure 7
The graphs related to Subcase 2.1 of Theorems3 and 4.Figure 8
The graphs related to Subcase 2.2 of Theorems3 and 4.Table 1
All possibilities for Case 3 of Theorems3 and 4.
GraphHGDG+5/3−n/21/2+2/3n−2DGV0,029/1525/1525/15V0,123/1013/613/6V1,18/38/38/3V0,rr≥2DG/2+13/15DG/2+2/3DG/2+2/3V1,rr≥2DG/2+11/15DG/2+2/3DG/2+2/3Vs,rs,r≥2DG/2+4/5DG/2+2/3DG/2+2/3Theorem 4.
LetG≠U6,41,1,U5,31,1 be a quasi-tree graph with n≥3 vertices, then(10)HG≥12+23n−2DG.The equality holds if and only ifG=V1,1 or Un,41,n−5.Proof.
The proof is similar to the proof of Theorem3. By induction on n, if n≤6, then Theorem 3 implies that the inequality holds unless when G=U6,41,1,U5,31,1.
LetG be a quasi-tree graph with n≥7 vertices. Suppose w is a vertex of G such that G−w is a tree. Let P=u0−u1−⋯−udG be the diametrical path of G. Since G−w is a tree, δG≤2. There exist three cases as follows.Case 1. There exists t∈G−P such that dt=1. Since t is not in diametrical path of G, DG=DG−t. Suppose Nt=r. So, such as Case 1 in the proof of Theorem 3, if G−t≠U6,41,1, then, by induction hypothesis,(11)HG≥HG−t+2drdr+1>12+23n−3DG>12+23n−2DG.IfG−t=U6,41,1, then G is one of the graphs which is shown with their harmonic indices in Figure 6. In this case, DG=4 and 1/2+2/3n−2DG=38/15. Hence, the inequality holds.Case 2. Every vertex of G−P is of degree at least 2, and there exists a vertex t∈G−P−w such that dt=2. From the previous case, DG=DG−t. Suppose Nt=r,s. Since dt=2, it is possible that G−t be a tree. There exist three subcases as follows.Subcase 2.1. G−t is not a tree and rands are not adjacent in G. By the same argument as in Subcase 2.1 of Theorem 3,(12)HG>HG−t+4dr−1drdr+12+dr+4ds−1dsds+12+ds>12+23n−2DG.IfG−t=U6,41,1, then 1/2+2/3n−2DG=38/15, and G is one of the graphs which are shown with their harmonic indices in Figure 7.Subcase 2.2. G−t is not a tree and rands are adjacent in G. By Subcase 2.2 of Theorem 3,(13)HG≥HG−t+2dr+4drdr+1dr+2+2ds+4dsds+1ds+2−4dr+dsds+dr−2>HG−t.So, by the induction hypothesis,(14)HG>12+23n−3DG>12+23n−2DG.IfG−t=U6,41,1, then 1/2+2/3n−2DG=38/15 and G is the graph which is shown with its harmonic index in Figure 8 and the inequality holds.Subcase 2.3. G−t is a tree. By the same argument as in the proof of Subcase 2.3 of Theorem 3, G is a unicyclic graph and by Theorem 3 in [18], HG≥1/2+2/3n−2DG, with equality when G=Un,41,n−5.Case 3. Every vertex of G−P is of degree at least 2, and if t∈VG and dt=2, then t∈u0,u1,…,ud,w. By the same argument as in Case 3 of Theorem 3, G−w is a path and VG=t∈u0,u1,…,ud∪w. Also, since G is not a tree, dw≥2 . If dw=2, then G is a unicyclic graph and by Theorem 3 in[18], HG≥1/2+2/3n−2DG, with equality if G=V1,1 or G=Un,41,n−5. Also, by Subcase 3.2 of Theorem 3, dw≯3. So, dw=3 and G is one of the graphs in Table 1. Obviously, HG≥1/2+2/3n−2DG, for all of them. As in Theorem 3, the inequality holds in all cases and the equality will be satisfy if and only if G=V1,1 or Un,41,n−5.



---

*Source: 6650407-2021-02-16.xml*