Journal of Applied Mathematics and Physics, 2013, 1, 5-6
http://dx.doi.org/10.4236/jamp.2013.13002 Published Online August 2013 (http://www.scirp.org/journal/jamp)
On Harmonic Index and Diameter of Graphs*
Jianxi Liu
School of Informatics, Guangdong University of Foreign Studies, Guangzhou, China
Received June 12, 2013; revised July 15, 2013; accepted August 5, 2013
Copyright © 2013 Jianxi Liu. This is an open access article distributed under the Creative Commons Attribution License, which
permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
ABSTRACT
The harmonic index of a graph is defined as G


 
2
uvE G
HG du dv


, where denotes the degree of a
vertex in . It has been found that the harmonic index correlates well with the Randi index and with the
-electronic energy of benzenoid hydrocarbons. In this work, we give several relations between the harmonic index
and diameter of graphs.

du
uGc
π
Keywords: Harmonic Index; Diameter
1. Introduction
All graphs considered in the following will be simple.
Let be a graph with vertex set and edge set
. The order of graph G is the number of its
vertices. The leaf of a graph is a vertex with degree one.
For undefined terminology and notations we refer the
reader to [1]. For a graph G, the harmonic index
G



VG
EG
H
G is defined as


 
2.
uvE G
HG du dv



It has been found that the harmonic index correlates
well with the Randić index [2,3] and the -electronic
energy of benzenoid hydrocarbons [4,5]. Favaron et al.
[6] considered the relation between harmonic index and
the eigenvalues of graphs. Zhong [7] found the minimum
and maximum values of the harmonic index for con-
nected graphs and trees, and characterized the cor-
responding extremal graphs. Recently, Wu et al. [8] gave
the minimum value of the Harmonic index among the
graphs with the minimum degree at least two. In this
work, we shall give some relations between the harmonic
index and diameter of graphs.
π
2. Main Results
First, we shall give two sharp upper bounds of the
relationship involving the harmonic index and diameter
of connected graphs. In [7], Zhong gave the following
result:
Lemma 2.1 ([7]) Let be a graph with order , Gn
then

,
2
n
HG

where the equality holds if and only if
G is a regular graph.
Since the complete graph n
K
is a regular graph with
diameter one, we have:
Theorem 2.2 Let be a connected graph with order G


4n diameter


DT , then
 

1,
22
HT
nn
HT DTDT

 
where equalities hold if and only if is the complete
graph
G
n
K
.
An edge 12
x
x

is called local maximum if its weight

12
x
2
dx d is maximum in its neighborhood, i.e.,
 


12
22
i
dx dxdx du


for any edge i
x
u for 1, 2.i

Lemma 2.3 Let 12
x
x be a local maximum edge in
graph , then
G




12 0.HGHG xx


*Research supported by the National Natural Science Foundation o
f
China (No.11101097) and Foundation for Distinguished Young Tal-
ents in HigherEducation of Guangdong, China (No.LYM11061). Proof. We have
C
opyright © 2013 SciRes. JAMP

J. X. Liu
6
  

  

  

  
 
   
   
12
21
12
121 1
1
221212 12
2
12 1212 12
222
1
2222 2
()1
11
22 2
10
11
uNx x
vNx x
HGHG xxdx dxdx dudx du
dx
dxdvdxdvdx dxdx dxdx dx
dx dx dxdx dxdx dxdx dx



 








 


 



 





,

where denotes the vertex set adjoining to

i
Nx i
x
for . 1, 2i
If 12
x
x is a leaf of , i.e., at least one of G


12
,
x
x
has degree one, we can see that it is a local maximum
edge. Thus, by Lemma 2.3,
Corollary 2.4 If 12
x
x is a leaf in graph G, then
 
12 0.HGHG xx
Theorem 2.5 Let T be a tree with order


4n
diameter , then

DT
 
 
51
,
6223 1
HT
n
HT DTDT n  
1

where equalities hold if and only if
T
is a path .
n
P
Proof. If is a path, we have
T

1
26
n
HT and

1DT n. It is obvious that both equalities hold.
Now we assume that
T
is not a path, then
and there are at least three pendent
vertices in

2DT n
T
. Assume 01
D
Puu u be the longest
path in
T
. Then at least one pendent vertex, say 1, is
not contained in
v
P
. Now we start an operation on
T
,
i.e., we continually delete pendent vertices which are not
contained in
P
until the resulting tree is
P
. Assume
1 are the vertices in the order they were deleted,
we have
,,
k
vv
 
1
1
1
23
k
i
i
D
HTHT vHTvHP


 



by Corollary 2.4 and
 
1
1
k
i
i
DTDT vDTvD





. Thus, we
have
 
>
51515
>
62 6262
H
TDTHPDP
Dn


 
n
and

  
15 1
2626
>= >
1
Dn
HT HP
DT DPDn

.
This result seems true for any connected graph with
order and we propose as a conjecture as follows:
n
Conjecture 2.6 Let be a connected graph with
order
G


4n diameter , then

DG
 
 
51
,
6223 1
HG
n
HG DGDG n  
1

.
REFERENCES
[1] J. A. Bondy and U. S. R. Murty, “Graph Theory,” Springer,
Berlin, 2008.
[2] X. Li, I. Gutman, “Mathematical Aspects of Randić-Type
Molecular Structure Descriptors,” Mathematical Chemis-
try Monographs No.1, University of Kragujevac, 2006.
[3] X. Li and Y. T. Shi, “A Survey on the Randić Index,”
Communications in Mathematical and in Computer
Chemistry, Vol. 59, No. 1, 2008, pp. 127-156.
[4] B. Lučić, N. Trinajstić and B. Zhou, “Comparison be-
tween the Sum-Connectivity Index and Product- Connec-
tivity Index for Benzenoid Hydrocarbons,” Chemical
Physics Letters, Vol. 475, No. 1-3, 2009, pp. 146-148.
doi:10.1016/j.cplett.2009.05.022
[5] B. Lučić, S. Nikolić, N. Trinajstić, B. Zhou and S. I. Turk,
“Sum-Connectivity Index,” In: I. Gutman and B. Furtula,
Ed., Novel Molecular Structure Descriptors-Theory and
Applications I, University of Kragujevac, Kragujevac,
2010, pp. 101-136.
[6] O. Favaron, M. Mahó and J. F. Saclé, “Some Eigenvalue
Properties in Graphs (Conjectures of Graffiti-II),” Dis-
crete Mathematics, Vol. 111 No. 1-3, 1993, pp. 197-220.
doi:10.1016/0012-365X(93)90156-N
[7] L. Zhong, “The Harmonic Index for Graphs,” Applied
Mathematics Letters, Vol. 25, No. 3, 2012, pp. 561-566.
doi:10.1016/j.aml.2011.09.059
[8] R. Wu, Z. Tang and H. Deng, “A Lower Bound for the
Harmonic Index of a Graph with Minimum Degree at
Least Two,” Filomat, Vol. 27, No. 1, 2013, pp. 51-55.