Hanyuan Denga , Selvaraj Balachandranb,c, Suresh Elumalaid, Toufik Mansourd

aCollege of Mathematics and Statistics, Hunan Normal University, Changsha, Hunan 410081, P.R. China bDepartment of Mathematics and Applied Mathematics, University of the Free State, Bloemfontein, South Africa

hydeng@hunnu.edu.cn, bala maths@rediffmail.com, sureshkako@gmail.com, tmansour@univ.haifa.ac.il

The sum of reciprocals of distance between any two vertices in a graph G is called the Harary index. We determine the n-vertex extremal graphs with the maximum Harary index for all bipartite graphs, a given matching number, a given vertex-connectivity, and with a given edge-connectivity, respectively.

Keywords: Harary index, bipartite graph, matching number, vertex-connectivity, edge-connectivity Mathematics Subject Classification : 05C15, 05C07, 05C50

DOI: 10.5614/ejgta.2019.7.2.12

1. Introduction

Throughout the paper let G be a connected graph with vertex set V (G) and the edge set E(G). We denote the degree of a vertex x in G by dG(x). We denote the distance of the shortest path between x, y 2 V (G) by dG(x, y).

A simple bipartite graph G = (V1, V2; E), is the union of disjoint vertex partitions V¹ and V2, such that none of the edges in G have both the end vertices in one partition. For every chosen two vertices from different partition in a bipartite graph are adjacent, then G is complete, denoted by Ka,b, where a = |V1| and b = |V2|.

Received: 18 October 2018, Revised: 12 May 2019, Accepted: 14 June 2019.

cDepartment of Mathematics, School of Arts, Sciences and Humanities, SASTRA Deemed University, Thanjavur, India

dDepartment of Mathematics, University of Haifa, 3498838 Haifa, Israel

A graph G is called k-connected if removing any set of k vertices from G, the result is a disconnected graph. In this context, the connectivity of G, denoted by \(\kappa(G)\). Similarly, a graph G is called G k'-edge-connected if removing any k' edges from G, the result is a disconnected graph. Here, the edge-connectivity of G, denoted by \(\kappa'(G)\).

Let \(\mathcal{A}_n^k\), \(\mathcal{C}_n^s\) and \(\mathcal{D}_n^t\) denote the set of all n-vertex bipartite graph with matching number k (see below), connectivity s and edge-connectivity t, respectively.

Since 1947, the distance-based graph invariant Wiener index is received a lot of attention, it is defined as

\[W(G) = \sum_{\{u,v\} \subseteq V(G)} d_G(u,v).\]

In an analogous way, Harary index [4, 8] defined as

\[H(G) = \sum_{\{u,v\} \subseteq V(G)} \frac{1}{d_G(u,v)}.\] (1)

Xu [14] determined the extremal results of Harary indices on trees. Xu and Das [16] characterized the extremal bicyclic and unicyclic graphs for H(G). Xu et al. [17] found the maximal H(G) for a fixed matching number on unicyclic graphs (for other example, see [1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 15, 18, 19, 20] and references cited therein).

Motivated by work of Li and Song [5], we determine the extremal graphs on n vertices with the maximum Harary index for all bipartite graphs with a given matching number, a given vertex-connectivity, and with a given edge-connectivity.

2. Harary index of bipartite graphs with a given matching number

We start by the following lemma, which holds immediately from the definitions.

Lemma 2.1. Let G be a simple graph with |V(G)| = n with \(G \not\cong K_n\). Then for every edge \(e \in E(\overline{G})\), where \(\overline{G}\) is the complement of G, H(G) < H(G + e).

In the next result, we present the extremal graph having the maximum H(G) for all bipartite graphs, for a fixed matching number.

Theorem 2.1. Let G represents a bipartite graph with n vertices and matching number k. Then \(K_{k,n-k}\) is the unique graph with the maximum Harary index.

Proof. By choosing G in \(\mathcal{A}_n^k\), such that its H(G) is very large. If \(k = \lfloor \frac{n}{2} \rfloor\), then using Lemma 2.1 we get, \(K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil}\) is maximum. So, we only consider \(k < \lfloor \frac{n}{2} \rfloor\).

Let G = (A, B; E) with \(|B| \ge |A| \ge k\) and M is the maximal matching in G. If |A| = k then we see that \(G = K_{k,n-k}\) is the extremal graph in G. By Lemma 2.1, H(G) increases by adding edges in G. So, we can assume that |A| > k.

Let \(A_M\), \(B_M\) be the vertex subsets of A, B which are incident to M. Then \(|A_M| = k\) and \(|B_M| = k\). It is noted that there is no edge in G between the set \(A - A_M\) of vertices and the set

\(B - B_M\) of vertices. If so, then the edges may be together with M to increase the size of the matching greater than M, which violates the maximality of M.

By attaching all the possible edges to the vertices of \(A_M\) and \(B_M\), \(A_M\) and \(B - B_M\), \(A - A_M\) and \(B_M\), we achieve a new graph G'. By Lemma 2.1, \(H(G) \leq H(G')\). Also, G' has the matching number at least k+1. So, \(G' \notin \mathcal{A}_n^k\) and \(G \ncong G'\). Now, we construct an another new graph G'' based on G', by deleting all the edges between the set \(A - A_M\) of vertices and the set \(B_M\) of vertices, and adding all the edges between \(A - A_M\) and \(A_M\) in G'. It is easy to verify that \(G'' \cong K_{k,n-k}\).

Let \(|A| = n_1\), \(|B| = n_2\), so \(n_1 + n_2 = n\) and \(n_2 \ge n_1 > k\) and using (1), we get

\[H(G') = k^{2} + k(n_{2} - k) + k(n_{1} - k) + \frac{C_{n_{1}}^{2} + C_{n_{2}}^{2}}{2} + \frac{(n_{1} - k)(n_{2} - k)}{3}\] \[= \frac{n_{1}^{2} + n_{2}^{2}}{4} + \frac{n_{1}n_{2}}{3} + \frac{2kn}{3} - \frac{n}{4} - \frac{2k^{2}}{3},\] \[H(G'') = k(n - k) + \frac{C_{k}^{2} + C_{n-k}^{2}}{2} = \frac{n^{2}}{4} + \frac{kn}{2} - \frac{n}{4} - \frac{k^{2}}{2}.\]

Therefore, by the fact that \(k < n_1 \le n_2 = n - n_1 < n - k\), we have

\[H(G') - H(G'') = \frac{kn - k^2 - n_1 n_2}{6} = \frac{k(n-k) - n_1 n_2}{6} < 0,\]

as required.

3. Harary index of bipartite graphs with a given vertex / edge-connectivity

In the current section, we determine the extremal graphs with the maximum Harary index among \(C_n^s\) and \(\mathcal{D}_n^t\).

By \(K_{p,0}\), \(p \ge 1\), we mean \(pK_1\) (p isolated vertices). Let \(O_s \lor_1 (K_{n_1,n_2} \cup K_{m_1,m_2})\) be the graph obtained by adding all vertices of the empty graph \(O_s\) of order \(s (s \ge 1)\) to all vertices belonging to the part of cardinality \(n_1\) in the bipartition of \(K_{n_1,n_2}\) and the part of cardinality \(m_1\) in the bipartition of \(K_{m_1,m_2}\), respectively.

Lemma 3.1. If s + q > p then

\[H(O_s \vee_1 (K_{1,0} \cup K_{p,q})) < H(O_s \vee_1 (K_{1,0} \cup K_{p+1,q-1})).\]

Proof. Let \(G = O_s \vee_1 (K_{1,0} \cup K_{p,q})\) and \(G' = O_s \vee_1 (K_{1,0} \cup K_{p+1,q-1})\). By (1), we have

\[H(G) = s + sp + pq + \frac{p + sq + C_s^2 + C_p^2 + C_q^2}{2} + \frac{q}{3}\]\[= \frac{3s}{4} + \frac{p}{4} + \frac{q}{12} + \frac{s^2 + p^2 + q^2}{4} + sp + pq + \frac{sq}{2}\]

and

\[\begin{split} H(G') = & s + (p+1)s + (q-1)(p+1) \\ & + \frac{(p+1) + s(q-1) + C_s^2 + C_{p+1}^2 + C_{q-1}^2}{2} + \frac{q-1}{3} \\ = & \frac{5s}{4} - \frac{p}{4} + \frac{7q}{12} + sp + pq + \frac{sq}{2} + \frac{s^2 + p^2 + q^2}{4} - \frac{1}{3}. \end{split}\]

So, by s + q > p, we have

\[H(G) - H(G') = \frac{p - (q + s)}{2} + \frac{1}{3} < 0,\]

as claimed.

Lemma 3.2. If s + q + 1 < p then

\[H(O_s \vee_1 (K_{1,0} \cup K_{p,q})) < H(O_s \vee_1 (K_{1,0} \cup K_{p-1,q+1})).\]

Proof. Let \(G = O_s \vee_1 (K_1 \cup K_{p,q})\) and \(G'' = O_s \vee_1 (K_1 \cup K_{p-1,q+1})\). By (1), we have

\[H(G) = s + sp + pq + \frac{p + sq + C_s^2 + C_p^2 + C_q^2}{2} + \frac{q}{3}\]\[= \frac{3s}{4} + \frac{p}{4} + \frac{q}{12} + \frac{s^2 + p^2 + q^2}{4} + sp + pq + \frac{sq}{2}\]

and

\[H(G'') = s + (p-1)s + (q+1)(p-1) + \frac{p-1+s(q+1)+C_s^2+C_{p-1}^2+C_{q+1}^2}{2} + \frac{q+1}{3}\]\[= \frac{s}{4} + \frac{3p}{4} - \frac{5q}{12} + sp + pq + \frac{sq}{2} + \frac{s^2+p^2+q^2}{4} - \frac{2}{3}.\]

Therefore, by s + q + 1 < p, we have

\[H(G) - H(G'') = \frac{s+q-p}{2} + \frac{2}{3} < 0,\]

as claimed.

Note that \(K_{s,n-s} = O_s \vee_1 (K_{1,0} \cup K_{n-s-1,0})\), by Lemma 3.2, we have

Corollary 3.1. If \(1 \le s \le \frac{n}{2} - 1\) then

\[H(K_{s,n-s}) < H(O_s \vee_1 (K_1 \cup K_{n-s-2,1})).\]

Lemma 3.3. Let \(G = (V_1, V_2; E) \in \mathcal{C}_n^s\) with a vertex-cut \(I = I_1 \cup I_2\) of order s such that G - I has two components \(G_1 = (A, B; E_1)\) and \(G_2 = (C, D; E_2)\), where \(V_1 = A \cup I_1 \cup C\) and \(V_2 = B \cup I_2 \cup D\). If \(A, C, I_1\) are non-empty sets, then G cannot be a graph with the maximum Harary index in \(\mathcal{C}_n^s\).

Proof. Assume that G has the maximum H(G) in \(C_n^s\). By Lemma 2.1, G contains all edges between \(V_1\) and \(V_2\), except edges between A and D and between C and B. Let \(|A| = m_1\), \(|B| = m_2\), \(|C| = n_1\), \(|D| = n_2\), \(|I_1| = k\) and \(|I_2| = t\). Then \(m_1 \ge 1\), \(n_1 \ge 1\), \(n_2 \ge 1\) and \(n_3 \ge 1\) and \(n_3 \ge 1\). So,

\[H(G) = m_1(m_2 + t) + k(m_2 + t + n_2) + n_1(t + n_2)\] \[+ \frac{m_1k + m_1n_1 + kn_1 + m_2n_2 + m_2t + n_2t + C_{m_1}^2 + C_k^2 + C_{n_1}^2 + C_{m_2}^2 + C_{n_2}^2 + C_t^2}{2}\] \[+ \frac{m_1n_2 + m_2n_1}{3}.\]

Note that \(G-(I_2\cup D)\) is not connected, we have \(t+n_2\geq s=t+k\), and \(n_2\geq k\). We partition D into \(D_1\) and \(D_2\) such that \(D=D_1\cup D_2\) with \(|D_1|=k\) and \(|D_2|=n_2-k\). Let \(u_0\) be any vertex of C, and \(G'=G-\{u_0v|v\in D_2\}+\{ad|a\in A,d\in D\}+\{bc|b\in B,c\in C-\{u_0\}\}\). Then \(G'\in \mathcal{C}_n^s\) with its bipartition \((V_1,V_2)\) and a vertex-cut \(I_2\cup D_1\) with s vertices. In fact, G' contains all edges between \(V_1\) and \(V_2\), except edges between \(u_0\) and \(B\cup I_2\), and

\[H(G') = (m_1 + k + n_1 - 1)(m_2 + t + n_2) + (t + k) + \frac{C_{m_1 + k + n_1}^2 + C_{m_2 + t + n_2}^2}{2} + \frac{m_2 + n_2 - k}{3}.\]

Thus,

\[H(G) - H(G') = -\frac{2}{3}(k + m_2(n_1 - 1) + n_2(m_1 - 1)) < 0,\]

a contradiction. \(\Box\)

Remark 3.1. By the symmetry, if \(B, D, I_2\) are non-empty sets (see Lemma 3.3), then G fails to be a maximum H(G) in \(\mathcal{C}_n^s\).

Let U and V any two vertex sets of G. Denote by \(E_G[U,V]\), edges of G with one of its end vertex in U and the other in V.

Lemma 3.4. Let n > 4 and \(G = (V_1, V_2; E) \in \mathcal{C}_n^s\) with an edge-cut \(E_t = E_1 \cup E_2\) of size t such that \(G - E_t\) has two components \(G_1 = (A, B; E')\) and \(G_2 = (C, D; E'')\), where \(V_1 = A \cup C\), \(V_2 = B \cup D\), \(E_1 = E_t \cap E_G[A, D]\) and \(E_2 = E_t \cap E_G[B, C]\). If A, B, C, D are non-empty sets, then G cannot be a graph with the maximum H(G) in \(\mathcal{D}_n^t\).

Proof. Assume that G has the maximum H(G) in \(\mathcal{D}_n^t\). By Lemma 2.1, G contains all edges between A and B, edges between C and D and edges in \(E_t\). Let \(|A| = m_1\), \(|B| = m_2\), \(|C| = n_1\), \(|D| = n_2\), \(|E_1| = a\) and \(|E_2| = b\). Then a + b = t and \(m_1 + n_1 + m_2 + n_2 = n > 4\).

Suppose, we assume \(m_1 > 1\) in the following. Let \(S_4, S_3, S_2\) and \(S_1\) denote the end-vertices of the edges of \(E_t\) in D, C, B and A, respectively. Let \(|A - S_1| = a_1, |B - S_2| = a_2, |C - S_3| = a_3\) and \(|D - S_4| = a_4\). Then G contains \(m_1m_2 + n_1n_2 + t = |E(G)|\) vertex pairs at distance 1, \(m_1n_2 + m_2n_1 - t\) vertex pairs at distance 3, and \(a_1a_3 + a_2a_4\) vertex pairs at distance 4. Remaining \(C_n^2 - |E_G| - (m_1n_1 + m_2n_2 - t) - (a_1a_4 + a_2a_3)\) vertex pairs are at distance 2. Therefore,

\[H(G) = |E(G)| + \frac{1}{3}(m_1n_2 + m_2n_1 - t) + \frac{1}{4}(a_1a_3 + a_2a_4) + \frac{1}{2}(C_n^2 - |E(G)| - (m_1n_2 + m_2n_1 - t) - (a_1a_3 + a_2a_4)).\]

Let \(c_0\) be a vertex and \(d_G(c_0) = h + |D| = h + n_2\), where \(h(\min\{b, m_2\} \ge h \ge 0)\) denotes the number of edges joining \(c_0\) to B. It is easy to see that the set of edges incident to \(c_0\) is an edge-cut of G, we have \(h + n_2 \ge t = a + b\) and \(|D| = n_2 \ge b \ge h\). We partition D into \(D_1\) and \(D_2\) such that \(D = D_1 \cup D_2\) with \(|D_1| = t - h\) and \(|D_2| = n_2 - t + h\). Let \(G' = G - \{c_0v|v \in D_2\} + \{ad|a \in A, d \in D\} + \{bc|b \in B, c \in C - \{c_0\}\}\). Then \(G' \in \mathcal{D}_n^t\)

with its bipartition \((V_1,V_2)\) and an edge-cut of edges joining \(c_0\) to the vertices in \(B \cup D_1\) of size t. In fact, G' contains all edges between \(A \cup C - \{c_0\}\) and \(B \cup D\), edges between \(c_0\) and \(c_0\) and \(c_0\) and \(c_0\) to \(c_0\). Then \(c_0\) contains \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to \(c_0\) to

\[|E(G')| + \frac{C_n^2 - |E(G')| - (m_2 + n_2 - t)}{2} + \frac{m_2 + n_2 - t}{3} = H(G').\]

Since A, B, C, D are non-empty sets and \(m_1 > 1\), then

\[H(G) - H(G') = -\frac{1}{4}(a_1a_3 + a_2a_4) - \frac{2}{3}m_2(n_1 - 1) - \frac{2}{3}n_2(m_1 - 1) < 0,\]

which is a contradiction.

Figure 1. Graphs \(H_1^*\), \(H_2^*\), \(H_3^*\) in Theorems 3.1 and 3.2.

Theorem 3.1. If \(C_n^s\) has the graph G with the maximum H(G), where \(1 \le s \le \frac{n}{2}\). Then \(G \in \{H_1^*, H_2^*, H_3^*\}\), where \(H_1^*, H_2^*\) and \(H_3^*\) are depicted in Figure 1.

Proof. Assume that, G has the maximum H(G) in \(C_n^s\). Let I be a vertex-cut of G having s vertices, and \(G_1, G_2, \dots, G_t\) are the components of G - I, where \(t \ge 2\).

If one of its components has a minimum of two vertices, then using Lemma 2.1 the component should be a complete bipartite.

If one of its components is a singleton i, then i must be adjacent to every vertex of I and the subgraph G[I] induced by I has no edges; or else \(\kappa(G) < s\). Therefore, I is contained in the same part of bipartition of G by Lemma 2.1.

Now, we consider the following cases:

• Case 1. If every component of G-I is a singleton, then \(G=K_{s,n-s}\). So \(t\geq \frac{n}{2}-1\) by Corollary 3.1. It is conventional to see that, for odd n, \(K_{s,n-s}\cong H_1^*\) and for even n, \(K_{s,n-s}\in\{H_2^*,H_3^*\}\).

• Case 2. If one of its component G-I has a minimum of two vertices. Then G-I has precisely two components; otherwise, we can get a graph \(G' \in \mathcal{C}_n^s\) by adding some edges in G such that the subgraph induced by \(V(G_1 \cup G_2 \cup \cdots \cup G_{t-1})\) is a complete bipartite graph, and H(G) < H(G') by Lemma 2.1, which is a contradiction. If G-I has two components \(G_1, G_2\), then by Lemma 3.3 and Remark 3.1, either \(G_1 = K_1\) or \(G_2 = K_1\). Let us assume that \(G_2 = K_1 = \{i\}\). Then, \(G_1 \cong K_{p,q}\) and u is joined to all vertices of I. So, I is contained in the same part of the bipartition of G, and each vertex of I is joined to all vertices in the same part of the bipartition of \(G_1\) by Lemma 2.1. Hence, \(G = O_s \vee_1 (K_{1,0} \cup K_{p,q})\), where s = |I|. And \(p \geq s\) since p vertices in the same part of the bipartition of \(K_{p,q}\) is a vertex-cut of \(K_{p,q}\). Since \(K_{p,q}\) is a graph in \(K_{p,q}\) with the maximum Harary index, and by Lemmas 3.1 and 3.2, we have \(K_{p,q} = K_{p,q} = K_{p,q}\) and \(K_{p,q} = K_{p,q} = K_{p,q}\) and \(K_{p,q} = K_{p,q} = K_{p,q}\) with the maximum Harary index, and by Lemmas 3.1 and 3.2, we have \(K_{p,q} = K_{p,q} = K_{p,q}\) and \(K_{p,q} = K_{p,q} = K_{p,q}\) with the maximum Harary index, and by Lemmas 3.1 and 3.2, we have \(K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q}\) and \(K_{p,q} = K_{p,q} = K_{p,q}\) such that \(K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q} = K_{p,q}\)

Using Lemma 3.4 and utilizing proof of the previous theorem, we conclude the following result.

Theorem 3.2. Let \(\mathcal{D}_n^t\) has the graph G with the maximum H(G) and \(1 \leq t \leq \frac{n}{2}\). Then \(G \in \{H_1^*, H_2^*, H_3^*\}\), where \(H_1^*, H_2^*\) and \(H_3^*\) are depicted in Figure 1.

Acknowledgement

The authors are very grateful to the referees for their careful reading, valuable suggestions, comments and corrections which resulted in a great improvement of the original manuscript. The Postdoctoral studies and research of the Suresh Elumalai is sustained by University of Haifa, Israel and it is deeply acknowledged.

References

• [1] M. Azari and A. Iranmanesh, Harary index of some nano-structures, MATCH Commun. Math. Comput. Chem. 71 (2014), 373–382.
• [2] H. Hua and M. Wang, On Harary index and traceable graphs, MATCH Commun. Math. Comput. Chem. 70 (2013), 297–300.
• [3] H. Hua and S. Zhang, On the reciprocal degree distance of graphs, Discrete Appl. Math. 160 (2012), 1152–1163.
• [4] O. Ivanciuc, T.S. Balaban and A.T. Balaban, Design of topological indices, part 4, reciprocal distance matrix, related local vertex invariants and topological indices, J. Math. Chem. 12 (1993), 309–318.
• [5] S. Li and Y. Song, On the sum of distances in bipartite graphs, Discrete Appl. Math. 169 (2014), 176–185.
• [6] S. Li, H. Zhang and M. Zhang, Further results on the reciprocal degree distance of graphs, J. Comb. Optim. 31 (2016), 648–668.

• [7] P. Padmapriya and V. Mathad, The eccentric-distance sum of some graphs, Electron. J. Graph Theory Appl. 5 (1) (2017), 51–62.
• [8] D. Plavssic, S. Nikoli ´ c, N. Trinajisti ´ c and Z. Mihali ´ c, On the Harary index for the characteri- ´ zation of chemical graphs, J. Math. Chem. 12 (1993), 235–250.
• [9] G. Su, L. Xiong and I. Gutman, Harary index of the k-th power of a graph, Appl. Anal. Discrete Math. 7 (2013), 94–105.
• [10] G. Su, L. Xiong, X. Su and X. Chen, Some results on the reciprocal sum-degree distance of graphs, J. Comb. Optim. 30 (2015), 435–446.
• [11] I. Tomescu, On the general sum-connectivity index of connected graphs with given order and girth, Electron. J. Graph Theory Appl. 4 (1) (2016), 1–7.
• [12] H. Wang and L. Kang, On the Harary index of cacti. Util. Math. 43 (2013), 369–386.
• [13] H. Wang and L. Kang, More on the Harary index of cacti, J. Appl. Math. Comput. 43 (2013), 369–386.
• [14] K. Xu, Trees with the seven smallest and eight greatest Harary indices, Discrete Appl. Math. 160 (2012), 321–331.
• [15] K. Xu and K.C. Das, On Harary index of graphs, Discrete Appl. Math. 159 (2011), 1631– 1640.
• [16] K. Xu and K.C. Das, Extremal unicyclic and bicyclic graphs with respect to Harary index, Bull. Malays. Math. Sci. Soc. 36 (2013), 373–383.
• [17] K. Xu, K.C. Das, H. Hua and M.V. Diudea, Maximal Harary index of unicyclic graphs with a given matching number, Stud. Univ. Babes-Bolyai. Chemia, 58 (2013), 71–86.
• [18] K. Xu, K.C. Das and N. Trinajstic, The Harary Index of a Graph, Springer, 2015. ´
• [19] K. Xu, M. Liu, K.C. Das, I. Gutman and B. Furtula, A survey on graphs with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem. 71 (2014), 461– 508.
• [20] K. Xu, J. Wang and H. Liu, The Harary index of ordinary and generalized quasi-tree graphs, J. Appl. Math. Comput. 45 (2014), 365–374.