# On the Resistance-Harary Index of Graphs Given Cut Edges

Authors: Hongzhuan Wang; Hongbo Hua; Libing Zhang; Shu Wen
Journal: Journal of Chemistry
 (2017)

---

## Abstract

Graphs are often used to describe the structure of compounds and drugs. Each vertex in the graph represents the molecule and each edge represents the bond between the atoms. The resistance distance between any two vertices is equal to the resistance between the two points of an electrical network. The Resistance-Harary index is defined as the sum of reciprocals of resistance distances between all pairs of vertices. In this paper, the extremal graphs with maximum Resistance-Harary index are determined in connected graphs with given vertices and cut edges.


---

## Body

## 1. Introduction

Recently, the development of computational chemistry owes much to the theory of graphs. One of the most popular areas is topological index. The molecular topological index can describe the molecular structure quantitatively and analyze the structure and performance of molecules.Among them, the most common topological index is resistance distance. The resistance distance is raised by Klein and Randić [1] as a distance function. Let G be a simple connected graph with vertex set V(G) and edge set E(G).The resistance distance between verticesu and v of G is recorded as rG(u,v), which represents the effective resistance between two nodes u and v in an electronic network; that is to say, the vertex corresponds to the node of the electronic network, and the edge corresponds to the unit resistance.Similar to the traditional path distance, the resistance distance not only has good mathematical characteristics but also has good physical characteristics [2, 3]; at the same time, it also has a good application in chemistry.Harary index is another kind of graph invariants proposed by Plavšić et al. [4] and by Ivanciuc et al. [5] in 1993 for the characterization of molecular graphs. Name this in honor of Professor Frank Harary’s birthday. The Harary index H(G) is defined as the sum of reciprocals of distances between all pairs of vertices of the graph G; that is, (1)HG=∑u,v⊆VG1du,v.Gutman [6] and Xu [7] investigated the Harary index of trees; they studied the Harary index of tree and pointed out that the path and the star attain the minimal and maximal value of Harary index, respectively, among a tree with given n vertices. In recent years, the Harary index was well studied in mathematical and chemical literatures [8].The reciprocal resistance distance is also called electrical conductance, Klein and Ivanciuc [9] investigated QSAR and QSPR molecular descriptors computed from the resistance distance and electrical conductance matrices, and they proposed the global cyclicity index C(G) as (2)CG=∑uv∈EG1ru,v-EG,where the sum is over all edges of G.In [10], using graph theory, electronic networks, and real number analysis methods, Yang obtains some conclusions about the global cyclicity index.Following the definition of the Harary index, Chen et al. [11] generalized the global cyclicity index and introduced Resistance-Harary index, defined as (3)RHG=∑u,v⊆VG1ru,v.In [11], Chen et al. depicted the graphs with largest and smallest Resistance-Harary index in all unicyclic graphs.All graphs considered in this paper are finite and simple.Before proceeding, we introduce some further notation and terminology. A cut edge is an edge whose deletion increases the number of components. Denote byKn, Cn, and Sn the complete, cycle, and star graph on n vertices, respectively. For a graph G with v∈V(G), G-v denotes the graph resulting from G by deleting v and its incident edges. For an edge uv of the graph G (the complement of G, resp.), G-uv (G+uv, resp.) denotes the graph resulting from G by deleting (adding, resp.) uv.For other definitions, we can refer to [12].In this thesis, we consider the Resistance-Harary index of graphs given cut edge. We will determine the graphs with maximum Resistance-Harary index in connected graphs given vertices and cut edges.


## 2. Some Preliminary Results

We first list or prove some lemmas as basic but necessary preliminaries.Lemma 1 (see [1, 13, 14]).
Letx be a cut vertex of a graph G, and let a and b be vertices in different components of G-x. Then (4)ra,b=ra,x+rx,b.Lemma 2.
The functionsf1(x)=x/2/x+m-x-1/2/(x-1)+m for x≥2 and m>0 and f2(x)=x/(2/x+A)(2/x+B) for x>1 and A>0, B>0 are strictly increasing.Proof.
By simple calculation,(5)f1′x=4x+x2m2+mx2-mx2-2mx+m+4x-42+mx-m2=4m2x-1+162+mx22+mx-m2>0.
Sincex≥2 and m>0, f1′(x) is the derivative of function f1(x) on x. Obviously, f1(x) is a strictly increasing function for x≥2 and m>0.
Similarly, we prove that the functionf2(x)=x/(2/x+A)(2/x+B) for x>1 and A>0, B>0 is also an increasing function. We finally obtain the result.Lemma 3.
LetG be a connected graph with at least three vertices. If G is not isomorphic to Kn, Let G∗=G+e, and then RH(G∗)>RH(G).Proof.
Suppose thatG is not a complete graph. Then there exists a pair of vertices vi and vj in G such that vivj∈E(G¯).
LetG∗=G+vivj, we have (6)RHG∗-RHG=RHG+vivj-RHG=∑1≤r<s≤n1rG∗vr,vs-1rGvr,vs=1rG∗vi,vj-1rGvi,vj+∑1≤r<s≤nr,s≠i,j1rG∗vr,vs-1rGvr,vs.We only to prove that rG∗(vi,vj)<rG(vi,vj); the proof of rG∗(vr,vs)<rG(vr,vs) for (r,s)≠(i,j) is similar. We distinguish the following two cases.
Case  1. vi and vj are vertices of cycle Cg in G, where g is the length of Cg.
Letd1(vi,vj) and d2(vi,vj) be distance between vi and vj in the cycle Cg, respectively. By the definition of resistance, we have (7)1rG∗vi,vj-1rGvi,vj=1d1vi,vj+1d2vi,vj+1-1d1vi,vj+1d2vi,vj>0.That is to say, rG∗(vi,vj)<rG(vi,vj).
Case  2. vi and vj are not vertices in any cycle of G.
In this case, we have(8)rG∗vi,vj-rGvi,vj=dGvi,vj1+dGvi,vj-dGvi,vj=dGvi,vj11+dGvi,vj-1<0.This completes the proof.Lemma 4.
Letxy∈E(G) be a cut edge in G, and let G1 and G2 be the two components of G-xy. Suppose further that x∈V(G1) and y∈V(G2), and then RH(G)=RH(G1)+RH(G2)+∑a∈V(G1)‍∑b∈V(G2)‍1/rG(a,x)+rG(b,y)+1.Proof.
By the definition of Resistance-Harary index and by Lemma1, we have (9)RHG=∑a,b∈VGi1rGa,b+∑a∈VG1∑b∈VG21rGa,b=RHG1+RHG2+∑a∈VG1∑b∈VG21rGa,x+rGb,y+1.
This completes the proof.Lemma 5.
LetG and G′ be the graphs in Figure 1, where G0 is a complete graph, and then RH(G)≤RH(G′), with equality if and only if x1=x2=⋯=xr.Figure 1
The graphs in Lemma5.Proof.
From the definition of the Resistance-Harary index and Lemma4, we have (10)RHG=∑1≤i<j≤n1rGvi,vj=∑i=0rRHGi+∑i=1r∑a∈VG0∑b∈VGi1rGa,b+∑1≤i<j≤r∑b∈VGi∑c∈VGj1rGb,c=∑i=0rRHGi+∑i=1r∑a∈VG0∑b∈VGi1rG0a,xi+rGiyi,b+1+∑1≤i<j≤r∑b∈VGi∑c∈VGj1rGib,yi+rGjc,yj+2+rG0xi,xj.Similarly, (11)RHG′=∑1≤i<j≤n1rG′vi,vj=∑i=0rRHGi+∑i=1r∑a∈VG0∑b∈VGi1rG′a,b+∑1≤i<j≤r∑b∈VGi∑c∈VGj1rG′b,c=∑i=0rRHGi+∑i=1r∑a∈VG0∑b∈VGi1rG0a,x1+rGiyi,b+1+∑1≤i<j≤r∑b∈VGi∑c∈VGj1rGib,yi+rGjc,yj+2. Since G0 is a complete graph, rG0(a,x1)=rG0(a,xi)=2/n0 for 1≤i≤r. And (12)RHG′-RHG=∑1≤i<j≤r∑b∈VGi∑c∈VGj1rGib,yi+rGjc,yj+2-1rGib,yi+rGjc,yj+2+rG0xi,xj≥0with equality if and only if rG0(xi,xj)=0; that is, x1=x2=⋯=xr. This completes the proof.Lemma 6.
LetG and G′ be the graphs depicted in Figure 2, where G2 and G3 are all complete graphs. Let ni be the number of vertices of Gi, where i=2,3. If n3>n2 and V(G4) may be an empty set, then RH(G′)>RH(G).Figure 2
The graphs in Lemma6.Proof.
By the definition of the Resistance-Harary index and Lemmas1 and 4, we have (13)RHG=∑1≤i<j≤n1rGvi,vj=∑i=14RHGi+∑i=24∑a∈VG1∑b∈VGi1rGa,b+∑2≤i<j≤4∑a∈VGi∑b∈VGj1rGa,b.Since G2 and G3 are all complete graphs, for any two vertices x,y∈V(Gi), we have rGi(x,y)=2/ni, where i=2,3. Similarly, we have (14)RHG′=∑1≤i<j≤n1rG′vi,vj=∑i=14RHGi+∑i=24∑a∈VG1∑b∈VGi1rG′a,b+∑2≤i<j≤4∑a∈VGi∑b∈VGj1rG′a,b,RHG′-RHG=∑a∈VG1∑b∈VG31rG1a,x1+rG3b,x3-1rG1a,x1+rG3b,x3+1-∑a∈VG1∑b∈VG21rG1a,x1+rG2b,x2-1rG1a,x1+rG2b,x2+1+∑a∈VG1∑b∈VG41rG1a,x1+rG4b,x4-1rG1a,x1+rG4b,x4+1.We just need to prove that (15)∇1=∑a∈VG1∑b∈VG31rG1a,x1+rG3b,x3-1rG1a,x1+rG3b,x3+1-∑a∈VG1∑b∈VG21rG1a,x1+rG2b,x2-1rG1a,x1+rG2b,x2+1>0.
In fact,(16)∇1=∑a∈VG1n3rG1a,x1+2/n3rG1a,x1+2/n3+1-n2rG1a,x1+2/n2rG1a,x1+2/n2+1.
In the following, we just need to prove that the fraction of∇1 is greater than zero. Denote ∇2 to be the fraction of ∇1; in fact, (17)∇2=rG1a,x12n3-n2+rG1a,x1n34+n2n2-4+n3n2n3+2n32+n2n22-2n2n3+2n32,=rG1a,x12n3-n2+rG1a,x14n32-n22+n2n3n3-n2n2n3+4n33-n23+2n1n3n32-n22n22n32>0. Since n3>n2, RH(G′)>RH(G). This completes the proof.


## 3. Characterization of the Maximizing Graph

In this section, we will characterize maximizing graph among all connected graphs withn vertices and k cut edges.First, we need some definitions below; letsk+1 be a star with vertex set {v0,v1,…,vk}, where v0 is the center of the star. In particular, the graph Sn(Kn0;Kn1,…,Knk) with ∑i=0k‍ni=n is obtained from Sk+1 by replacing the vertex vi by Kni for i=0,1,2,…,k. By the definition of Resistance-Harary index, it is not difficult to obtain RH(Kn)=n2(n-1)/4. If G0 is a complete graph, for any vertices x0,a∈V(G0), there is rG0(a,x0)=2/n0.Lemma 7.
Letn and n0,n1,…,nk(k≥1) be positive integers such that n0≥n1≥⋯≥nk, n1>1, and n0+n1+⋯+nk=n. Let G=Sn(Kn0,Kn1,…,Knk) (see Figure 3) and G′=Sn(Kn0+1,Kn1-1,…,Knk). Then RH(G′)>RH(G).Figure 3
The graphs in Lemma7 and in Theorem 9.Proof.
By direct calculation, we have(18)RHG=RHSnKn0;Kn1,…,Knk=∑i=0kRHKni+∑i=1k∑a∈VKn0∑b∈VKni1rGa,b+∑1≤i<j≤k∑b∈VKni∑c∈VKnj1rGb,c=14∑i=0kni2ni-1+∑i=1k∑a∈VKn0∑b∈VKni1rGa,x0+rGb,xi+1+∑1≤i<j≤k∑b∈VKni∑c∈VKnj1rGb,xi+rGc,xj+2=14∑i=0kni2ni-1+∑i=1kn02/n0+2/ni+1+∑1≤i<j≤k∑b∈VKni∑c∈VKnj12/ni+2/nj+2. Similarly, we can deduce the value of RH(G′). Then (19)RHG′-RHG=14n0+12n0-n02n0-1+n1-12n1-2-n12n1-1+n0+12/n0+1+2/n1-1+1-n02/n0+2/n1+1+∑i=2kn0+12/n0+1+2/ni+1-n02/n0+2/ni+1+∑i=2kn1-12/n1-1+2/ni+2-n12/n1+2/ni+2. In order to prove that the result RH(G′)>RH(G), we distinguish three steps in the following. Denote (20)△1=14n0+12n0-n02n0-1+n1-12n1-2-n12n1-1-n02/n0+2/n1+1,△2=n0+12/n0+1+2/n1-1+1,△3=∑i=2kn0+12/n0+1+2/ni+1-n02/n0+2/ni+1+n1-12/n1-1+2/ni+2-n12/n1+2/ni+2.
Obviously,△2>0. In the following, we first prove that △1>0. By direct calculation, we have (21)△1=143n02+n0-3n12+5n1-2-n02/n0+2/n1+1=n1-12+3n02-3n12+n0+3n14-n02n12n1+2n0+n0n1=n1-12+3n0n1n0-n1+3n0n1n02-n1242n1+2n0+n0n1+6n03-n13+8n0n1+2n02+6n1242n1+2n0+n0n1>0 (since n0≥n1>1). Secondly, we will prove that △3>0. (22)△3=∑i=2kn0+12/n0+1+2/ni+1-n02/n0+2/ni+1-n12/n1+2/ni+2-n1-12/n1-1+2/ni+2>∑i=2kn0+12/n0+1+2/ni+1-n02/n0+2/ni+1-n12/n1+2/ni+1-n1-12/n1-1+2/ni+1>0, where the second inequality is due to the fact that(23)n12/n1+2/ni+1-n1-12/n1-1+2/ni+1-n12/n1+2/ni+2-n1-12/n1-1+2/ni+2=n12/n1+A2/n1+B-n1-12/n1-1+B2/n1-1+A,where A=2/ni+1, B=2/ni+2, and the function f(x)=x/(2/x+A)(2/x+B) is an increasing function, and then (24)n12/n1-2/ni+1-n1-12/n1-1+2/ni+1>n12/n1+2/ni+2-n1-12/n1-1+2/ni+2.By Lemma 2, the last inequality is due to the fact the function f2(x)=x/2/x+A-x-1/2/(x-1)+A for x≥2 and 0<A≤3 is an increasing function.
By combination with above discussion, we haveRH(G′)>RH(G), which finishes the proof of Lemma 7.Corollary 8.
Suppose thatRH(Sn(Kn0;Kn1,…,Knk)) is defined as above and n0≥n1≥n2≥⋯≥nk, the value of RH(Sn(Kn0;Kn1,…,Knk)) reaches its maximum value at n0=n-k and n1=n2=⋯=nk=1.Theorem 9.
IfG is a connected graph with k cut edges and n vertices, then (25)RHG≤n-k2n-k-14+k2+3k4+n-k-1n-kkn-k+2, with equality if and only if G≅Sn(Kn-k;K1,K1,…,K1) (see Figure 3).Proof.
To determine the maximum Resistance-Harary index of the graph, we select such a connected graph so that it cut off all the cut edges for a complete graph by Lemma3. Moreover, we can further choose G=Sn(Kn0;Kn1,…,Knk) by Lemmas 5 and 6, and let ∑i=0k‍ni=n, n0=max⁡{n0,n1,…,nk}. From the definition of the Resistance-Harary index and Lemma 4, we have(26)RHG=RHSnKn0;Kn1,…,Knk=14∑i=0kni2ni-1+∑i=1k∑a∈VKn0∑b∈VKni1rGa,x0+rGb,xi+1+∑1≤i<j≤k∑b∈VKni∑c∈VKnj1rGb,xi+rGc,xj+2=14∑i=0kni2ni-1+∑i=1kn02/n0+2/nj+1+∑1≤i<j≤k∑b∈VKni∑c∈VKnj12/ni+2/nj+2≤n-k2n-k-14+k2+3k4+kn-kn-k-1n-k+2. By Lemma 7 and Corollary 8, we know that the equality holds if and only if n0=n-k, n1=n2=⋯=nk=1; that is, G≅Sn(Kn-k;K1,…,K1). This completes the result.Corollary 10.
IfT is a tree with n vertices, then RH(G)≤n2+n-2/4, with equality if and only if T≅Sn.Proof.
SinceT is a tree with n vertices, it has n-1 cut edges, and RH(G)≤n2+n-2/4 with equality if and only if T≅Sn by Theorem 9. This completes the result.


## 4. Conclusion

In this thesis, we considered the Resistance-Harary index of graphs with given number of cut edges and describe a graph with a maximum Resistance-Harary index. A problem raised naturally at this moment is, among all connected graphs withn vertices and k cut edges, which graph has the minimum Resistance-Harary index? We will continue to consider this problem in the nearest future.



---

*Source: 3531746-2017-12-21.xml*