On Harmonic Index and Diameter of Graphs

doi:10.4236/jamp.2013.13002

Paper Menu >>

Journal Menu >>

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

Email: [email protected], [email protected]

Received June 12, 2013; revised July 15, 2013; accepted August 5, 2013

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



 

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.



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 is defined as



 

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





where the equality holds if and only if

G is a regular graph.

Since the complete graph n

is a regular graph with

diameter one, we have:

Theorem 2.2 Let be a connected graph with order G





4n diameter





DT , then

 



HT DTDT



 

where equalities hold if and only if is the complete

graph

An edge 12



is called local maximum if its weight



dx d is maximum in its neighborhood, i.e.,

 



dx dxdx du





for any edge i

u for 1, 2.i



Lemma 2.3 Let 12

x be a local maximum edge in

graph , then









12 0.HGHG xx





*Research supported by the National Natural Science Foundation o

China (No.11101097) and Foundation for Distinguished Young Tal-

ents in HigherEducation of Guangdong, China (No.LYM11061). Proof. We have

J. X. Liu

  



  



  



  



   



 



121 1

221212 12

12 1212 12

222

2222 2

()1

22 2

uNx x

vNx x

HGHG xxdx dxdx dudx du

dxdvdxdvdx dxdx dxdx dx

dx dx dxdx dxdx dxdx dx





 













 





 





 









where denotes the vertex set adjoining to



Nx i

for .

1, 2i

If 12

x is a leaf of , i.e., at least one of G





has degree one, we can see that it is a local maximum

edge. Thus, by Lemma 2.3,

Corollary 2.4 If 12

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



 

 

6223 1

HT DTDT n

 



where equalities hold if and only if

is a path .

Proof. If is a path, we have



HT and



1DT n. It is obvious that both equalities hold.

Now we assume that

is not a path, then

and there are at least three pendent

vertices in



2DT n

. Assume 01

Puu u be the longest

path in

. Then at least one pendent vertex, say 1, is

not contained in

. Now we start an operation on

i.e., we continually delete pendent vertices which are not

contained in

until the resulting tree is

. Assume

1 are the vertices in the order they were deleted,

we have

vv

 

HTHT vHTvHP





 







by Corollary 2.4 and

 

DTDT vDTvD











. Thus, we

have

 

51515

62 6262

TDTHPDP





 

and



 



15 1

2626

>= >

HT HP

DT DPDn



.

This result seems true for any connected graph with

order and we propose as a conjecture as follows:

Conjecture 2.6 Let be a connected graph with

order





4n diameter , then



 

 

6223 1

HG DGDG n

 



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.