﻿On the Harmonic Index of Triangle-Free Graphs

Applied Mathematics
Vol.4 No.8(2013), Article ID:35482,3 pages DOI:10.4236/am.2013.48161

On the Harmonic Index of Triangle-Free Graphs*

Jianxi Liu

Department of Applied Mathematics, School of Informatics, Guangdong University of Foreign Studies, Guangzhou, China

Email: liujianxi2001@gmail.com, ljx@oamail.gdufs.edu.cn

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.

Received June 7, 2013; revised July 7, 2013; accepted July 14, 2013

Keywords: Harmonic Index; Minimum Degree; Triangle-Free

ABSTRACT

The harmonic index of a graph is defined as , where denotes the degree of a vertex in . In this work, we give another expression for the Harmonic index. Using this expression, we give the minimum value of the harmonic index for any triangle-free graphs with order and minimum degree for and show the corresponding extremal graph is the complete graph .

1. Introduction

All graphs considered in the following will be simple. Let be a graph with vertex set and edge set . The order and size of graph are the number of its vertices and number of its edges, respectively. For undefined terminology and notations, we refer the reader to .

For a graph , the harmonic index is defined as It has been found that the harmonic index, which is a special case of general sum-connectivity index, correlates well with the Randić index [2,3] and the -electronic energy of benzenoid hydrocarbons [4,5]. In , Favaron et al. considered the relation between harmonic index and the eigenvalues of graphs. Zhong  found the minimum and maximum values of the harmonic index for connected graphs and trees, and characterized the corresponding extremal graphs. Recently, Wu et al.  give a best possible lower bound for the harmonic index of a graph (a triangle-free graph, respectively) with order and minimum degree at least two and characterize the extremal graphs. In this work, we will give a best possible lower bound for the harmonic index of a triangle-free graph with order and minimum degree at least . We show the corresponding extremal graph is the complete bipartite graph .

2. Another Expression for the Harmonic Index

Before we go forwards to investigate the relationship between the Harmonic index and the minimum degree of triangle-free graphs, we will give another expression for the Harmonic index in this section, which is vital in sequel.

Let be a graphs with order and minimum degree . Denote by  , the number of edges joining the vertices of degrees and . Denote by the number of vertices of degree of . Then (1) (2)

By counting the edges that incident to a vertex of degree , , one obtains (3)

Substituting Equation (3) back into Equation (2) and performing appropriate rearrangements, we get (4)

Now, rewriting Equation (1) as (5)

and combining Equations (4) and (5) so as to eliminate the term , we arrive at i.e., (6) (7)

Remark 2.1 From (7), we see that for vertex graph and the equality holds if and only if is regular.

3. Main Results

First, we give a lower bound for any triangle-free graph with order and size .

Lemma 3.1 For any triangle-free graph with order and size , then where equality holds if and only if is of the form for some natural numbers , and .

Proof. For any edge of , we have , or it would contain triangle(s). By (1), we have equality holds if and only if for every . Thus, if we denote for an edge , then each of the neighbors, including , of should has degree . Similarly, each of the neighbors of has degree . Therefore, and .

Lemma 3.2 Let , for then is decreasing in and increasing in .

Proof. We have and for .

Theorem 3.3 Let be a triangle-free graph with order and the minimum degree  . Then where equality holds if and only if .

Proof. Assume is the size of graph . We divide the proof into the following two cases.

Case 1. . The result follows by Lemma 3.1.

Case 2. . Note that the maximum degree for graph , or it would contain triangle(s). By (6) and Lemma 3.2, we have For equalities to hold above, we must have , which means that .

REFERENCES

1. J. A. Bondy and U. S. R. Murty, “Graph Theory,” Springer, 2008. doi:10.1007/978-1-84628-970-5
2. X. Li and I. Gutman, “Mathematical Aspects of Randic’- Type Molecular Structure Descriptors,” Mathematical Chemistry Monographs, Vol. 1, Kragujevac, 2006.
3. X. Li and Y. T. Shi, “A Survey on the Randić Index,” MATCH: Communications in Mathematical and in Computer Chemistry, Vol. 59, No. 1, 2008, pp. 127-156.
4. B. Lučić, S. Nikolić, N. Trinajstić, B. Zhou and S. I. Turk, “Sum-Connectivity Index,” In: I. Gutman and B. Furtula, Eds., Novel Molecular Structure Descriptors-Theory and Applications I, University of Kragujevac, Kragujevac, 2010, pp. 101-136.
5. B. Lučić, N. Trinajstić and B. Zhou, “Comparison between the Sum-Connectivity Index and Product-Connectivity Index for Benzenoid Hydrocarbons,” Chemical Physics Letters, Vol. 475, No. 1-3, 2009, pp. 146-148. doi:10.1016/j.cplett.2009.05.022
6. O. Favaron, M. Mahó and J. F. Saclé, ”Some Eigenvalue Properties in Graphs (Conjectures of Graffiti-II),” Discrete 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.

NOTES

*Research supported by the National Natural Science Foundation of China (No.11101097) and Foundation for Distinguished Young Talents in Higher Education of Guangdong, China (No.LYM11061).