# Extremal Harary Index of Graphs with Given Number of Vertices of Odd Degree

Authors: Zhenhua Su; Zikai Tang; Hanyuan Deng
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

The Harary index is one of the most investigated topological indices in mathematical chemistry and in related disciplines, which can be used to describe the molecular structure and physical properties. LetGn,2k be the set of all connected graphs on n vertices with exactly 2k vertices of odd degree. Recently, the graphs in Gn,0 with the first four maximal Harary index and the first minimal Harary index are determined. In the paper, by using the edge-deleted method and some combinatorial skills, we characterize the graph in Gn,2k with the maximal Harary index for all 0≤k≤n/2, the graphs in Gn,2 with the first two minimal Harary index, and the graph in Gn,4 with the minimal Harary index. These results will be conducive to the further study of Harary index and its applications.


---

## Body

## 1. Introduction

In mathematical chemistry, topological index (Wiener index, Szeged index), is a mathematical invariant derived from the structure diagram of a compound. It is used to characterize some property of the graph of a molecule. In the sequel, this simple numerical representation of a molecule has shown to be a very useful quantity to use in the quantitative structure-property relationships (QSPR)[1]. Moreover, it also has many applications in facility location, communication, cryptology, etc.TheWiener index was first introduced by Wiener in 1947 when calculating the boiling point of alkanes, it is a graph invariant based on distances in a graph. It is denoted by WG and defined as the sum of distances between all pairs of vertices in G, i.e.,(1)WG=∑u,v∈VGdGu,v,where the distance between vertices u and v of G, denoted by dGu,v, is the number of edges on a shortest path connecting these vertices in G.TheHarary index of a graph G, denoted by HG, is another distance-based topological index of G. It has been introduced independently by Plavaic et al. [2] and Ivanciuc et al. [3], and it is defined as follows:(2)HG=∑u,v∈VG1dGu,v,where the summation goes over all unordered pairs of vertices of G.For a vertexv∈VG, let d^Gv=∑u∈VG\v1/dGu,v, then the Harary index of G can be rewritten as follows:(3)HG=12∑v∈VGd^Gv.The Harary index is also one of the most investigated topological indices in mathematical chemistry and in related disciplines. The Harary index has several interesting properties. Some of these are listed in [2]. For example, (1) the Harary index appears to be a convenient measure of the compactness of the molecule. The larger the Harary index, the larger the compactness of the molecule. The Harary index may also be used as a convenient measure of branching in alkane trees. In compact structures, the number of short distances increases, hence the Harary index is larger than in the case of extended structures. Similarly, a more branched structure has more short distances and the Harary index is, thus, also larger for more branched structures. (2) The Harary index and its variants was used for modeling eight representative physical properties: boiling points, molar volumes, molar refractions, heats of vaporization, critical temperatures, critical pressures, surface tensions, and melting points of the 74 alkanes from ethane to nonanes. These statistical results show that (i) the most accurate QSPR model for predicting the heats of vaporization is the biparametric model with the Harary index and (ii) the most accurate QSPR model for predicting the surface tensions is the biparametric model with the Harary index. For a review, historical details, and further bibliography on the chemical applications of the Harary index, see [1, 4–6].An Euler tour is a closed walk in a graph that traverses every edge exactly once. A graph is Eulerian if it admits an Euler tour, and a graph is Eulerian if and only if it is connected and all its vertices have even degrees. Recently, the Wiener index of an Eulerian graph was considered in [7, 8]. Cai et al. [9] characterized the Eulerian graphs with the first four maximal Harary indices and proved that the cycle is the unique graph minimizing the Harary index among all Eulerian graphs of given order.Note that an Eulerian graph has no vertex of odd degree. This leads naturally to determine the extremal values of some topological indices and characterize the extremal graphs among all graphs with given number of vertices of odd degree. In 2013, Lin [10] characterized the trees which maximize and minimize the Wiener index among all odd-vertex-degree trees (i.e., trees that have only vertices of odd degrees) of given order, and Furtula [11] characterized the trees with the second, third, ..., seventeenth maximal Wiener index among all odd-vertex-degree trees of given order. In 2014, Lin et al. [12] also characterized the trees that minimize and maximize the Wiener index among all trees with given number of vertices of even degree, respectively. Recently, Su et al. [13] characterized the graph with the minimum Wiener index among all connected graphs on n vertices with exactly 2k vertices of odd degree for all 0≤k≤n/2 and the graph with the first two maximal Wiener index among all connected graphs on n vertices with exactly 2 vertices of odd degree. For more results about Harary index, reader can refer to [14–18].In this paper, we continue to study the extremal Harary index of graphs with2k vertices of odd degree. Specially, they are Eulerian for k=0. Let Gn,2k be the set of all n-vertex graphs with exactly 2k vertices of odd degree, where 0≤k≤n/2. By using the edge-deleted method and some combinatorial skills, we characterize the graph in Gn,2k with the maximal Harary index for all 0≤k≤n/2, the graphs in Gn,2 with the first two minimal Harary index and the graph in Gn,4 with the minimal Harary index. These results are the further in-depth study and generalization of [9] and also can be applied to get the properties of related alkanes similar to the structure of Gn,2k, which will greatly enrich the application of Harary index.


## 2. Graphs with the Maximal Harary index

Denote byKn the complete graph on n vertices. If n is odd, then Kn has no vertex of odd degree. If n is even, then all vertices in Kn are of odd degree. Let Mt be a set of t independent edges from Kn. Then, Kn/Mt∈Gn,2k, where t=k for odd n and t=n/2−k for even n.Figure 1
The graph F_{n, 3}.Theorem 1.
(i)
Ifn is odd, then the unique graph among Gn,2k with the maximal Harary index is Kn\Mt;(ii)
Ifn is even, then the unique graph Gn,2k with the maximal Harary index is Kn\Mn/2−k.Proof.
LetG∈Gn,2k, VG=v1,v2,…,vn, and v1,v2,…,v2k all vertices of odd degree in G.
Ifn is odd, then dGvi≤n−2 and at least one vertex in G is not adjacent to vi, d^Gvi=∑vj∈VG\vi1/dGvj,vi≤1/2+1+⋯+1=n−3/2for 1≤i≤2k. Moreover, d^Gvj≤1+1+⋯+1=n−1 for 2k+1≤j≤n. So, we have the following equation:(4)HG12∑v∈VGd^Gv≤122kn−32+n−2kn−1=12n2−n−k2=1n−k2.
With equality if and only ifdGvi=n−22k+1≤j≤n and dGvj=n−12k+1≤j≤n, i.e.,G≅Kn\Mk.
Ifn is even, then dGvj≤n−2 and at least one vertex in G is not adjacent to vj, d^Gvj≤1/2+1+⋯+1=n−3/2 for 2k+1≤j≤n. Moreover, d^Gvi≤1+1+⋯+1=n−1 for 1≤i≤2k. So, we have the following equation:(5)HG=12∑v∈VGd^Gv≤122n−1+n−2kn−32=12n2−3n4+k2=n2+k2−n4.
With equality if and only ifdGvi=n−11≤i≤2k and dGvj=n−22k+1≤j≤n, i.e.,G≅Kn\Mn/2−k.
Specially, takingk=0, we can get the graph with the maximal Harary index among all Eulerian graphs of order n.Corollary 1.
(see Cai et al. [9])(i)
Ifn is odd, then the unique Eulerian graph of order n with the maximal Harary index is Kn.(ii)
Ifn is even, then the unique Eulerian graph of order n with the maximal Harary index is Kn\Mn/2 (the cocktail-party graph).


## 3. Graphs with the Minimal Harary index

In this section, we consider the elements with the minimal Harary index amongGn,2k. For k=0, it was shown in [9] that the cycle Cn on n vertices is the unique graph with the minimal Harary index among Gn,0 (all Eulerian graphs on n vertices). Now, for k=1, we will determine the graphs with the first and the second minimal Harary index among Gn,2.Note thatPn∈Gn,2, and it is well-known that for any graph G on n vertices [6],(6)HG≥1+n∑i=2n−11i.With equality if and only ifG is the path Pn on n vertices. Therefore, we haveTheorem 2.
Pn is the unique graph with the minimal Harary index among Gn,2, and HPn=1+n∑i=2n−11/i.
LetTn−3,1,1 be the tree on n vertices obtained by attaching a path of length n−4 to a pendant vertex of the star S4. In [19], it was shown that Tn−3,1,1 is the unique tree with the second minimal Harary index among all trees on n vertices. And Tn−3,1,1∈Gn,4, by using HG−e<HG for any edge e in G, we can get that Tn−3,1,1 is the unique graph with the minimal Harary index among Gn,4, i.e.,Theorem 3.
Tn−3,1,1 is the unique graph with the minimal Harary index among Gn,4.
LetFn,3 be the graph on n vertices obtained by attaching a path of length n−3 to a vertex of a triangle K3. Then, Fn,3∈Gn,2. The following result gives the graph with the second minimal Harary index among Gn,2k.Theorem 4.
Fn,3 is the unique graph with the second minimal Harary index among Gn,2, and HFn,3=4+n−2/2+n∑i=2n−31/i.Proof.
SincePn is the unique tree inGn,2, the graph with the second minimal Harary index among Gn,2 is not a tree. It is known in [20] that Fn,3 is the unique unicyclic graph on n vertices with the minimal Harary index, and HFn,3=4+n−2/2+n∑i=2n−31/i. Also, HG−e<HG for any edge e in G, we deduce that Fn,3 is the unique graph with the second minimal Harary index among Gn,2.


## 4. Conclusion

Harary index originates from the description of molecular structure and calculating the boiling point of alkanes, which is widely applied in chemistry, physics, biology, and other fields. In the present paper, by using the edge-deleted method and some combinatorial skills, we characterize the graphs amongGn,2k with the greatest, the first and the second smallest Harary index.From [9], if n is odd, then the graphs with the first-maximal, second-maximal, third-maximal, and fourth-maximal Harary index among Gn,0 are Kn, the graphs obtained from Kn by deleting the edges of a triangle, of a quadrangle, and of a pentagon, respectively; if n is even, then the graphs with the first-maximal, second-maximal, third-maximal, and fourth-maximal Harary index among Gn,0 are the cocktail-party graph CPn, the graphs are obtained from CPn by deleting the edges of a triangle, quadrangle, and pentagon, respectively.The graph with the first minimal Harary index amongGn,0 is Cn. Based on our results, the graph with the maximal Harary index among Gn,2k for 0≤k≤n/2 is characterized, the graphs with the first- and second-minimal Harary index among Gn,2k for k=0,1 are characterized and the graphs with the minimal Harary index among Gn,4 is characterized.In terms of application, Harary index not only be used as a convenient measure of branching in alkane trees, but also was used for modeling several representative physical properties, such as boiling points, molar volumes, molar refractions, heats of vaporization, critical temperatures, critical pressures, and so on. Therefore, according to our results, we can get the properties of related alkanes similar to the structure ofGn,2k, which will greatly enrich the application of Harary index.Finally, these results lead to the following problem.Problem 1.
What is the minimal Harary index and the extremal graph amongGn,2k, where 3≤k≤n/2.



---

*Source: 4916308-2022-09-20.xml*