# The Harary Index of All Unicyclic Graphs with Given Diameter

Authors: Bao-Hua Xing; Gui-Dong Yu; Li-Xiang Wang; Jinde Cao
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

The Harary index ofG is the sum of reciprocals of distance between any two vertices in G. In this paper, we obtain the graphs with the maximum and second-maximum Harary indices among n-vertex unicyclic graphs with diameter d.


---

## Body

## 1. Introduction

In this paper, all graphs are simple, undirected, and connected. Denote byE(G1), V(G1) the edge set and vertex set of G1 and EG1, VG1 the number of edges and vertices in G1, respectively. When EG1=VG1, the graph G1 is called a unicyclic graph. Let d(x) (or dG1(x)), NG1(x) be the degree and the neighborhood of a vertex x in G1, respectively. When d(x)=1, we call x is a pendant vertex. The distance between x1 and y1  (x1,y1∈V(G1)) is denoted by dG1(x1,y1). The diameter d of G1 is d=max⁡{dG1x1,y1∣∀x1,y1∈VG1}. The graph G1-x1y1 (or G1+x1y1) arisen by deleting the edge x1y1∈E(G1) (or by adding a new edge x1y1∉E(G1)). Let Pk and Ck be the path and cycle with VPk=VCk=k, respectively. Denote by P=v0v1⋯vk(k≥1) a path of G1, where dG1(v1)=dG1(v2)=⋯=dG1(vk-1)=2 (if k>1). When dG1(v0)≥3, dG1(vk)≥3, P is an internal path of G1. When dG1(v0)≥3,dG1(vk)=1, P is a pendant path of G1. If k=1, specially, P is a pendant edge. When the subgraph P1 is P itself, where P1 is induced by V(P) in G1, P is an induced path. For other terminologies and notations, we refer the readers to [1].The Harary indexH(G1), has been introduced independently in [2, 3]. Its calculation is as follows: (1)HG1=∑x1,y1∈VG11dG1x1,y1,where dG1(x1,y1) is defined as above and the sum goes over all the pairs of vertices in G1.The set ofn-vertex unicyclic graphs with diameter d is denoted by Un,d. The graph ∆n,d1 (see Figure 1) on n vertices arisen from Pd=v0v1⋯vd by attaching n-d-2 pendant edges to vd/2 and adding a new vertex vd+1 to be adjacent to vd/2 and vd/2+1.Figure 1
The graphs∆n,d1 and ∆n,d2.The graph∆n,d2 (see Figure 1) arisen from Pd=v0v1⋯vd by attaching n-d-2 pendant edges to vd/2+1 and adding a new vertex vd+1 to be adjacent to vd/2 and vd/2+1. The n-vertex graph arisen from Pd=v0v1⋯vd by attaching n-d-3 pendant edges to vd/2 and adding two new adjacent vertices vd+1 and vd+2 to be adjacent to vd/2, denoted by ∇n,d (see Figure 2). So, if d=2, the graph ∇n,2 arisen from C3 by attaching n-3 pendant edges to one vertex of C3.Figure 2
The graphs∇n,d and Ud+2.Note thatn-vertex graph ∆n,d3 arisen from Pd=v0v1⋯vd by attaching n-d-3 pendant edges to vd/2 and one pendant edge to vd/2+1 and adding a new vertex vd+1 to be adjacent to vd/2 and vd/2+1. ∆n,d4 arisen from Pd=v0v1⋯vd by attaching n-d-2 pendant edges to vd/2 and adding a new vertex vd+1 to be adjacent to vd/2 and vd/2+1.LetPd=v0v1⋯vd, U0(vi) be the graph with d+2 vertices arisen from Pd by adding a new vertex u0 to be adjacent to one vertex vi(vi∈V(Pd),1≤i≤d-1). Pd(C3;vi) arisen from Pd=v0v1⋯vd by attaching n-d-3 pendant vertices to vi(1≤i≤d-1) and identifying vi with one vertex of C3, denote Un,d1={Pd(C3;vi)∣1≤i≤d-1}. Let Ud+2 be a (d+2)-vertex unicyclic graph arisen from Pd=v0v1⋯vd by adding a new vertex vd+1 to be adjacent to vk and vk+1 (see Figure 2), Ud+2(n-d-2;vj) arisen from Ud+2 by attaching n-d-2 pendant vertices to vj(1≤j≤d-1,orj=d+1), and denote Un,d2={Ud+2(n-d-2;vj)∣1≤j≤d-1,orj=d+1}.Lately, the investigations on the spectral radius or eigenvalue or topological index of a special class of graphs and the topological properties of a certain class of networks remain a popular topic to researchers. For example, J.Q. Fei and J.H. Tu [4] characterized the complete characterization of the degree Kirchhoff index of bicyclic graphs. J.B. Liu et al. [5] discussed the topological properties of certain neural networks. B. Ning and B. Li [6] discussed the spectral radius of connected claw-free graphs. Y.Y. Wu and Y.J. Chen [7] analyzed the eccentric connectivity index of graphs. C. Wang et al. [8] obtained the least eigenvalue of the graphs whose complements are connected and have pendant paths. Many results can be seen in [2–16] and other papers. In particular, A. Ilic et al. [13] discussed the Harary index among the trees with fixed diameter. In this paper, we determine the graphs which have the maximum and second-maximum Harary indices among all the n-vertex unicyclic graphs with diameter d.


## 2. Lemmas

Lemma 1 (see [14]).
LetA, H1, and H2 be three connected, pairwise disjoint graphs; note that u1,u2∈V(A), v1∈V(H1), w1∈V(H2). The graph G is obtained by identifying the vertices u1, v1 and u2, w1 between A, H1, H2, respectively. G′ is obtained by identifying the vertices u1, v1, w1 from A, H1, H2 and G′′ is obtained by identifying the vertices u2, v1, w1 from A, H1, H2; then we can get (2)HG<HG′orHG<HG′′.Lemma 2 (see [9]).
LetG1 be an n-vertex unicyclic graph and ∇n,2 be the graph defined as above. Then(3)HG1≤H∇n,2,if and only if G1≅∇n,2, and the equality holds. When d=1, then G1≅C3, and when d=2, n≤5, then G1≅C4.Lemma 3.
LetU0(vi) be the graph defined as above; then (4)HU0vd/2≥HU0vi;if and only if i=d/2, the equality holds.Proof.
By the calculation of Harary index, we can get the following.
(1) If1≤i<d/2, (5)HU0vi+1-HU0vi=1i+2-1d-i+1>0.
(2) Ifd/2<i≤d-1, (6)HU0vi-1-HU0vi=1d-i+2-1i+1>0.
Whend is odd, we can get H(U0(vd/2))=H(U0(vd/2+1)).
Thus the result holds.Lemma 4.
LetUn,d2={Ud+2(n-d-2;vj)∣1≤j≤d-1,orj=d+1} and ∆n,d1 and ∆n,d2 be the set and two graphs defined as above, respectively. G1∈Un,d2; then(7)HG1≤H∆n,d1;if and only if G1≅∆n,d1, the equality holds.Proof.
Choose a graphG1∈Un,d2(3≤d≤n-2), such that H(G1) is the maximum. The following claims play a crucial role.
Claim 1. j∈{k,k+1,d/2,d/2+1}.
Proof. First, we prove j≠d+1. Otherwise, j=d+1; denote ui∈NG1(vd+1)∖{vk,vk+1}, 1≤i≤n-d-2; let(8)G1∗=G1-∑i=1n-d-2vd+1ui+∑i=1n-d-2vkuiorG1∗=G1-∑i=1n-d-2vd+1ui+∑i=1n-d-2vk+1ui;using Lemma 1, we get H(G1)<H(G1∗), a contraction.
So,1≤j≤d-1, let wi∈NG1(vj)∖{vj-1,vj+1}, 1≤i≤n-d-2, NPd(vj)={vj-1,vj+1}.
(1) If1≤j<k≤d/2, let (9)G1∗=G1-∑i=1n-d-2vjwi+∑i=1n-d-2vkwi;
ifd/2≤k<k+1<j≤d-1, let (10)G1∗=G1-∑i=1n-d-2vjwi+∑i=1n-d-2vk+1wi.
(2) If1≤k+1<j≤d/2 or d/2≤j<k<k+1≤d-1, let (11)G1∗=G1-vd+1vk-vd+1vk+1+vd+1vj+vd+1vj+1.
(3) If1≤j<d/2<k,k+1≤d-1, let (12)G1∗=G1-∑i=1n-d-2vjwi-vd+1vk-vd+1vk+1+∑i=1n-d-2vd/2wi+vd+1vd/2+vd+1vd/2+1;i.e., G1∗≅∆n,d1;
if1≤k<k+1<d/2+1<j≤d-1, let (13)G1∗=G1-∑i=1n-d-2vjwi-vd+1vk-vd+1vk+1+∑i=1n-d-2vd/2+1wi+vd+1vd/2+vd+1vd/2+1;i.e., G1∗≅∆n,d2.
From Lemma3 and the calculation of H(G1), we can calculate that H(G1)<H(G1∗), a contraction.
Claim 2. k=d/2.
Proof. Otherwise, if k=j<d/2, let G1∗=G1-vd-1vd+v0vd; if k=j>d/2, let G1∗=G1-v0v1+v0vd. From Lemma 3, we can get H(G1)<H(G1∗), a contraction.
By Claims 1-2, we have the graphG1≅∆n,d1 or G1≅∆n,d2.
Claim 3. H(∆n,d2)≤H(∆n,d1).
Proof. If d=2t is even, we have(14)H∆n,d2-H∆n,d1=H∆n,2t2-H∆n,2t1=n-2t-21+1t+1+1t+2+2∑i=2t1i-1+2∑i=2t+11i=n-2t-21t+2-1t+1<0.
Ifd=2t+1 is odd, ∆n,2t+11≅∆n,2t+12, H(∆n,d1)-H(∆n,d2)=0.
By Claims 1-3, we haveG1≅∆n,d1.
Thus the result follows.


## 3. Main Results

In this section, we will list our main results.Theorem 5.
LetUn,d and ∆n,d1 be defined in Section 1, the n-vertex graph G1∈Un,d(3≤d≤n-2); then (15)H∆n,d1≥HG1;if and only if G1≅∆n,d1, the equality holds.Proof.
LetG1∈Un,d; using Lemma 2, the result holds for d=1,2. If d=n-1, then G1≅Cn. So, we discuss that 3≤d≤n-2.
Choose a graphG1∈Un,d with H(G1) being the maximum. Note that Cq is the only cycle and Pd=v0v1⋯vd is the induced path in G1; assume that d(v0)=1; we consider the following claims.
Claim 1. VCq⋂VPd>0.
Proof. Otherwise, suppose that there exists a path Pk=vhvg+1⋯vg+k-1vl connecting the cycle Cq and the path Pd with vh∈V(Pd),vl∈V(Cq); denote us∈NG1(vh)∖{vg+1},1≤s≤d(vh)-1 and wj∈NG1(vl)∖{vg+k-1},1≤j≤d(vl)-1. Let (16)G1∗=G1-∑s=1dvh-1vhus+∑s=1dvh-1vlusorG1∗=G1-∑j=1dvl-1vlwj+∑j=1dvl-1vhwj.
Then, applying Lemma1, H(G1)<H(G1∗), a contraction.
Using Claim 1, we note thatV(Cq)∩V(Pd)={vt,vt+1,⋯,vt+k}, V(Cq)∖V(Pd)={vd+1,vd+2,⋯,vs}.
Claim 2. For any v∈V(G1)∖(V(Pd)⋃V(Cq)), d(v)=1.
Proof. Otherwise, assume that there exists a vertex u∈V(G1)∖(V(Pd)⋃V(Cq)) with uvb(1≤b≤d(u)-1),uvf∈E(G1), vb∈V(G1)∖(V(Pd)⋃V(Cq)), vf∈V(Pd)⋃V(Cq). Suppose that us′∈NG1(vf)∖{u}, 1≤s≤d(vf)-1. Let (17)G1∗=G1-∑s=1dvf-1vfus′+∑s=1dvf-1uus′orG1∗=G1-∑b=1du-1vbu+∑b=1du-1vbvf.Then, using Lemma 1, H(G1)<H(G1∗), a contraction.
By Claim 2, we have any vertexv∈V(G1)∖(V(Pd)⋃V(Cq)) is pendant vertex.
Claim 3. VCq∩VPd≤2.
Proof. Otherwise, suppose that V(Cq)∩V(Pd)={vt,vt+1,⋯,vt+k}, k≥2.
(1) Ift≤d/2-1, denote ui∈NG1(vt)∖{vs,vt-1,vt+1}, 1≤i≤d(vt)-3 (if exists), NPd(vt)={vt-1,vt+1}. Let (18)G1∗=G1-vsvt+vsvt+1-∑i=1dvt-3vtui+∑i=1dvt-3vt+1ui.
(2) Ift+k≥d/2+2, denote us∈NG1(vt+k)∖{vd+1,vt+k-1,vt+k+1}, 1≤s≤d(vt+k)-3 (if exists), NPd(vt+k)={vt+k-1,vt+k+1}. Let (19)G1∗=G1-vd+1vt+k+vd+1vt+k-1-∑s=1dvt+k-3vt+kus+∑s=1dvt+k-3vt+k-1us.
Then, applying Lemma3 and the calculation of H(G1), H(G1)<H(G1∗), a contraction.
Claim 4. (1) if|V(Cq)∩V(Pd)|=2, s=d+1; (2) if|V(Cq)∩V(Pd)|=1, s=d+2.
Proof. (1) Otherwise, we assume that s≥d+2. The graph G1∗ arisen by deleting all edges in E(Cq) of G1 and incidence with Cq except the edges vtvt+1,vt+1vd+1 of G1, adding the edge vtvd+1, connecting all isolated vertices to the vertex vt (if t≥d/2) or to the vertex vt+1 (if t+1≤d/2) of G1. Together with the definition of the Harary index and Lemma 3, H(G1)<H(G1∗), a contraction.
(2) Otherwise, we assume thats≥d+3. The graph G1∗ is obtained from G1 by deleting all edges in E(Cq) and incidence with Cq except the edges vtvd+1,vd+1vd+2, adding the edge vtvd+2, connecting all isolated vertices to the vertex vt. We can calculate that H(G1)<H(G1∗), a contraction.
By Claim 4 and Lemmas1 and 3, we get G1∈Un,d1⋃‍Un,d2. If G1∈Un,d1, applying Lemma 3, G1≅∇n,d (see Figure 2); if G1∈Un,d2, applying Lemma 4, G1≅∆n,d1.
Claim 5. H(∆n,d1)>H(∇n,d).
Proof. If d=2t is even, we have(20)H∆n,d1-H∇n,d=H∆n,2t1-H∇n,2t=1t+1+2∑i=1t1i+12-1+2∑i=2t+11i+1=12-1t+1>0.
Ifd=2t+1 is odd, we have(21)H∆n,d1-H∇n,d=H∆n,2t+11-H∇n,2t+1=2∑i=1t+11i+12-1+2∑i=2t+11i+1t+2+1=12-1t+2>0.
By Claims 1-5, we haveG1≅∆n,d1.
Thus the result follows.Theorem 6.
LetUn,d,∆n,d1 be defined in Section 1; the graph G1∈Un,d∖{∆n,d1}(3≤d≤n-2); then
(1) Ifd=2t is even, we obtain (22)H∇n,d≥HG1,when2n≥t2+5t+2;if and only if G1≅∇n,d, the equality holds. (23)H∆n,d2≥HG1,when4t+8≤2n≤t2+5t+2;if and only if G1≅∆n,d2, the equality holds.
(2) Ifd=2t+1 is odd, we have (24)H∆n,d4≥HG1;if and only if G1≅∆n,d4, the equality holds.Proof.
Choose a graphG1∈Un,d∖{∆n,d1}, such that H(G1) is as large as possible; together with Lemmas 1, 3, and 4 and Theorem 5, we have the following.
(1) Ifd=2t is even, G1≅∆n,d2 or G1≅∆n,d3 or G1≅∇n,d.
In fact,(25)H∆n,d3-H∆n,d2=n-d-3116+2∑i=2t+11i-n-d-32+2∑i=2t1i+1t+1+1t+2=n-d-31t+1-1t+2-16<0,H∆n,d3-H∇n,d=32+2∑i=2t1i+1t+1+1t+2+n-d-33-2+2∑i=2t+11i+n-d-32=-1t+1t+2-12-n-d-36)<0,H∇n,d-H∆n,d2=n-d-32+2∑i=2t+11i-n-d-32+2∑i=2t1i+1t+1+1t+2+3+4∑i=2t+11i-72+4∑i=2t1i+2t+1+1t+2=n-d-21t+1-1t+2+1t+1-12.
(1.1) When2n≥t2+5t+2, H(∇n,d)-H(∆n,d2)≥0.
(1.2) When4t+8≤2n≤t2+5t+2, H(∇n,d)-H(∆n,d2)≤0.
(2) Ifd=2t+1 is odd, H(∆n,d1)=H(∆n,d2), so G1≅∆n,d3 or G1≅∆n,d4 or G1≅∇n,d.(26)H∆n,d3-H∆n,d4=13n-d-3-12n-d-3+3+1t+2+4∑i=2t+11i-3+2t+2+3∑i=2t+11i+∑i=2t1i=n-d-313-12+1t+1-1t+2<0,H∇n,d-H∆n,d4=3+2t+2+4∑i=2t+11i-72+2t+2+3∑i=2t+11i+∑i=2t1i=1t+1-12<0.
Thus the result follows.



---

*Source: 3957023-2018-09-16.xml*