Extremal Bipartite Graphs with Given Parameters on the Resistance–Harary Index

Abstract

Resistance distance is a concept developed from electronic networks. The calculation of resistance distance in various circuits has attracted the attention of many engineers. This report considers the resistance-based graph invariant, the Resistance–Harary index, which represents the sum of the reciprocal resistances of any vertex pair in the figure G, denoted by $RH\left(G\right)$. Vertex bipartiteness in a graph G is the minimum number of vertices removed that makes the graph G become a bipartite graph. In this study, we give the upper bound and lower bound of the $RH$ index, and describe the corresponding extremal graphs in the bipartite graph of a given order. We also describe the graphs with maximum $RH$ index in terms of graph parameters such as vertex bipartiteness, cut edges, and matching numbers.

1. Introduction

There are graph invariants that describe certain properties of a graph, which we call topological indices. Various topological indices are proposed and researched by both theoretical chemists and mathematicians. Topological index is mainly used to study the quantitative relationship between structure and performance and between structure and activity. It would be helpful for describing partially biological and chemical properties. Some of them have been proved to be successful [1]. Recently, finding the extreme value for the topological indices, as well as the related problem of characterizing the extremal graphs, attracted the attention of many researchers, and many results were obtained.

Among these topological indices, one of most widely known topological description is the Wiener index, which was proposed in 1947 and represents the sum of the distances of all pairs of vertices in the graph, i.e.,

$$W\left(G\right)=\sum _{\{u,v\}\in V\left(G\right)}{d}_G(u,v).$$

Another graph invariant based on distance is called the Harary index, has been introduced independently by Placšić et al. [2] and by Ivanciuc et al. [3] in 1993, which is the sum of the reciprocal distances of any vertex pair in graph G, i.e.,

$$H\left(G\right)=\sum _{\{u,v\}\in V\left(G\right)}\frac{1}{d_G(u,v)}.$$

More results on the Harary index can be found in the literature [4,5,6,7].

Recently, graph invariants based on resistance distance have attracted the attention of theorists, such as the Kirchhoff index. The resistance distance is what Klein and Randić [8] came up with as a function of the distance of the graph. The resistance distance between two vertices u and v of G, denoted by $r_G(u,v)$, represents the effective resistance of two elements u and v in a circuit, and each edge in G means the cell resistance.

Similar to the distance in the path graph, the resistance distance is also closely related to the structure of the graph, and not only has good mathematics and physics characteristics [9,10], but also has widespread chemistry applications.

The Kirchhoff index is one of the most studied topological indices, which is defined as

$$kf\left(G\right)=\sum _{\{x,y\}\subseteq V\left(G\right)}{r}_G(x,y).$$

With the continuous development and improvement of electrical network theory, D.J. Klein and O. Ivanciue [11] investigated the global cyclictiy index $C\left(G\right)$, defined as

$$C\left(G\right)=\sum _{uv\in E\left(G\right)}[\frac{1}{r_G(u,v)}-\frac{1}{d_G(u,v)}],$$

Y. Yang [12] obtained some results on global cyclicity index.

Inspired by the Harary index, S. Chen et al. [13] modify the global cyclicity index and put forward the Resistance–Harary index, described as

$$RH\left(G\right)=\sum _{\{u,v\}\subseteq V\left(G\right)}\frac{1}{r_G(u,v)}.$$

In [14], the structure of the graph with maximum $RH$ value is described among the connected graph with given order and cut edges.

All graphs considered here are connected and simple. Let G be a graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$, and the degree of each vertex v is expressed as $d_G\left(v\right)$, which means the number of neighbors of v in G. $d_G(u,v)$ is the distance between u and v in G, the longest distance between any two vertices in the graph is called the diameter.

As usual, let $C_n$, $S_n$ and $P_n$ be a cycle, a star, and a path with n vertices, respectively. $G-uv$ represents the subgraph obtained by deleting an edge $uv$ from graph G. Similarly, $G+uv$ represents the graph obtained by adding an edge $uv$ to graph G. Let U and W be all the vertex sets of G. Where $W\subseteq U$, then $U\backslash W$ represents the complement of W in U. The pendant vertex of G refers to the vertex of graph G with degree 1. The pendant edge is the edge adjacent to the pendant vertex.

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets X and Y, such that every edge connects a vertex in X to one in Y. Vertex sets X and Y are usually called the parts of the graph. If a graph G is a bipartite graph, and all vertices in X are connected to all vertices in Y, then G is a completed bipartite graph.

If the number of vertices in each part of the completed bipartite is m and n, respectively, denoted it by $K_{m,n}$. The cut vertex (edge) will increase the number of branches of the graph if it is removed. Other terms not defined here are referred to [15].

A matching M in graph G is a set of non-adjacent edges, that is, no two edges share a common vertex. A maximum matching (also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number of a graph G is the size of a maximum matching.

Inspired by the above results, it is natural to consider these extremal problems from the class of general connected graphs to the bipartite graphs. Our aim in this article is to study the extremal bipartite graphs with given parameters on Resistance–Harary index. First, we give the upper bound and lower bound of $RH$ index, and describe the corresponding extremal graphs in the bipartite graph of a given order. We also describe the graphs with maximum $RH$ index in terms of graph parameters such as vertex bipartiteness $v_b$, (where $1\le v_b\le n-2$), cut edges, and matching numbers.

2. General Connected Bipartite Graphs

In this section, we give the upper bound and lower bound of $RH$ index, and describe the corresponding extremal graphs in the bipartite graph of a given order. In the simple connected acyclic graph, the Resistance distance and distance from the two points in the graph are equal, that is, the Resistance–Harary index and the Harary index are the same in the acyclic graph. There is a formula for this scenario:

$$RH\left(P_n\right)=H\left(P_n\right)=1+n\sum _{i=2}^{n-1}\frac{1}{i}.$$

However, when the connected graph contains cycles, the resistance distance is different from the general distance. Our calculation is based on electrical network theory, given a fixed resistor on each edge, the shortest distance between two vertices represents the effective resistance of the corresponding two components in the circuit. Let $C_k=u_1{u}_2\dots u_k{u}_1$ be the cycle on k vertices, where $k\ge 3$. By Ohm’s law, any two components in a circuit $u_s,u_t\in V\left(C_k\right)$ with $s<t$, we have

$$\frac{1}{r_{C_k}(u_s,u_t)}=\frac{1}{t-s}+\frac{1}{k-(t-s)},$$

then, we have

$$r_{C_k}(u_s,u_t)=\frac{(t-s)(k+s-t)}{k}.$$

We start with some useful lemmas.

Lemma 1

([8]). w is the cut vertex of graph G, and let u and v be two vertices of different components of $G-w$. There must be $r_G(u,v)=r_G(u,w)+r_G(w,v)$.

Lemma 2

([14]). Let G be a graph that is not complete. Add an edge from G and we get the graph $G^{*}$. So there is $RH\left(G^{*}\right)>RH\left(G\right)$. That is to say, $RH\left(G\right)$ increases with addition of edges.

Corollary 1.

G is a connected graph with n vertices, and H is a connected spanning subgraph of G. Then $RH\left(H\right)\le RH\left(G\right)$, the equal sign is true when $G\cong H$.

Lemma 3

([13]). Let T be a tree on n vertices different from $P_n$ and $S_n$. Then

$$RH\left(P_n\right)<RH\left(T\right)<RH\left(S_n\right).$$

Theorem 1.

$K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$ is the graph with maximum $RH$ index among all connected bipartite graphs of order n.

Proof. 

Choose $G^0$ as the graph such that its Resistance–Harary index is as large as possible, let $(X,Y)$ be its two divisions, where $\left|X\right|+\left|Y\right|=n$. We first prove the following two claims.

Claim 1.$G^0$ is a complete bipartite graph.

Suppose to the contrary that $G^0=(X,Y)$ is a graph that is not complete. Thus we can add one edge from $u\in X$ to $v\in Y$ to form a new graph $G^0+uv$. It is obvious that $G^0+uv$ is still a bipartite graph. By Lemma 2, we know that $RH(G^0+uv)>RH\left(G^0\right)$, which contradicts the maximality of $G^0$.

Claim 2.$G^0\cong K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$.

From Claim 1, we denote $G^0$ as $K_{s,t}$. In a complete connected bipartite graph $K_{s,t}$, Klein [16] obtain that the resistance distance between vertices from X and Y, respectively, is $\frac{s+t-1}{st}$. The resistance distance between any two vertices in X and in Y is $\frac{2}{t}$ and $\frac{2}{s}$, respectively, hence, by Lemma 1 and the definition of $RH$ index, we can get that

$$\begin{array}{ccc}\hfill RH\left(K_{s,t}\right)& =& \frac{st}{s+t-1}st+\frac{s}{2}\left(\genfrac{}{}{0pt}{}{t}{2}\right)+\frac{t}{2}\left(\genfrac{}{}{0pt}{}{s}{2}\right),\hfill \\ \hfill & =& \frac{s^2{t}^2}{s+t-1}+\frac{st(t-1)}{4}+\frac{st(s-1)}{4},\hfill \\ \hfill & =& \frac{st(4st+{(s+t)}^2-3(s+t)+2)}{4(s+t-1)}.\hfill \end{array}$$

$$\begin{array}{c}\hfill RH\left(K_{s-1,t+1}\right)=\frac{(s-1)(t+1)(4(s-1)(t+1)+{(s+t)}^2-3(s+t)+2)}{4(s+t-1)}.\end{array}$$

Let $M={(s+t)}^2-3(s+t)+2$, if $s>t+1$, then, we have

$$\begin{array}{ccc}\hfill RH\left(K_{s-1,t+1}\right)-RH\left(K_{s,t}\right)& =& \frac{\left[\right(s-1\left)\right(t+1\left)\right(4(s-1)(t+1)+M)-st(4st+M\left)\right]}{4(s+t-1)},\hfill \\ \hfill & =& \frac{4{(s-1)}^2{(t+1)}^2+M(s-1)(t+1)-4s^2{t}^2-M·st}{4(s+t-1)},\hfill \\ \hfill & =& \frac{4(s-t-1)(2st+s-t-1)+M(s-t-1)}{4(s+t-1)},\hfill \\ \hfill & >& 0.\hfill \end{array}$$

Then,

$$\begin{array}{c}\hfill RH\left(K_{s-1,t+1}\right)>RH\left(K_{s,t}\right).\end{array}$$

So $RH\left(K_{s,t}\right)$ obtain the extremal value if and only if $K_{s,t}\cong K_{\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil }$. This completes the proof. ◻

Theorem 2.

For any bipartite graph G of order n, we have

$$\begin{array}{c}\hfill 1+n\sum _{i=2}^{n-1}\frac{1}{i}\le RH\left(G\right)\le \frac{\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil (4\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil +n^2-3n+2)}{4(n-1)}.\end{array}$$

Proof. 

By Lemma 3 and Corollary 1, we can deduce that $P_n$ has minimal $RH$ index in the bipartite graphs of order n. By Theorem 1, one can see that $K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$ has the maximum Resistance–Harary index. By direct calculation, we have

$$\begin{array}{c}\hfill RH(K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil })=\frac{\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil (4\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil +n^2-3n+2)}{4(n-1)}\end{array}$$

and

$$\begin{array}{c}\hfill RH\left(P_n\right)=H\left(P_n\right)=1+n\sum _{i=2}^{n-1}\frac{1}{i}.\end{array}$$

This completes the proof. ◻

3. Bipartite Graphs Given Number of Matchings

In this section, we are going to characterize the extremal bipartite graphs of order n with given matching number q for the Resistance–Harary index.

Lemma 4.

The function for $f\left(x\right)=\frac{x^2{q}^2}{x+q-1}$ for $q>1$ and $x>q$ is strictly increasing.

Proof. 

Now, let us compute the derivative of this function

$$\begin{array}{ccc}\hfill f^{\prime }\left(x\right)& =& \frac{2x{q}^2(x+q-1)-x^2{q}^2}{{(x+q-1)}^2},\hfill \\ \hfill & =& \frac{x^2{q}^2+2x{q}^3-2x{q}^2}{{(x+q-1)}^2},\hfill \\ \hfill & =& \frac{x^2{q}^2+2x{q}^2(q-1)}{{(x+q-1)}^2},\hfill \\ \hfill & >& 0.\hfill \end{array}$$

This completes the proof. ◻

Theorem 3.

Graph $K_{q,n-q}$ has the largest $RH$ in the bipartite graphs of order n given matching number q.

Proof. 

We assume that G is a bipartite graph of a given matching number q, and $(U,W)$ is its vertex partition, and G has the largest $RH$ index. Obviously, $q\le \lfloor \frac{n}{2}\rfloor$, if $q=\lfloor \frac{n}{2}\rfloor$, by Lemma 2 and Theorem 1, the extremal graph happens to be isomorphic to $K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$, as expected. We are going to prove that, $q<\lfloor \frac{n}{2}\rfloor$, naturally, we make $\left|W\right|\ge \left|U\right|$ and take $\left|M\right|=q$ as the maximal matching of G, by Lemma 2, the value of the Resistance–Harary index is increasing when we increase the number of edges. So if $\left|U\right|=q$, the extremal graph $G\cong K_{q,n-q}$. Next, we consider $\left|U\right|>q$. Let $U_M$, $W_M$ be the vertex subset sets in U, W saturated with M, respectively. Then, $|U_M|=|W_M|=q$. By the maximality of M, we infer that there are no edges set between $U\backslash U_M$ and $W\backslash W_M$. Add as many edges between the vertices of $U_M$ and $W_M$, $U_M$ and $W\backslash W_M$, $U\backslash U_M$ and $W_M$ as we can from G, we get the result graph $G^{{}^{\prime }}$. Note that $W\backslash W_M\ne \varnothing$ and $U\backslash U_M\ne \varnothing$ and $G^{{}^{\prime }}$ has at least $q+1$ matching number. So, $G\ne G^{\prime }$ and by Lemma 2, we have $RH\left(G^{\prime }\right)>RH\left(G\right)$. We get another bipartite graph $G^{″}$ by separating two vertices sets of $U\backslash U_M$ and $W_M$ and associating two sets of $U\backslash U_M$ and $U_M$ in graph $G^{\prime }$. Obviously, $G^{″}$ is isomorphic to the complete bipartite graph $K_{q,n-q}$, which has the matching number q. Next, we will prove that

$$RH\left(G^{″}\right)>RH\left(G^{\prime }\right).$$

Let $|U\backslash U_M|=n_1$, $|W\backslash W_M|=n_2$. Suppose that $n_2\ge n_1$, we partition $V_{G^{\prime }}=V_{G^{″}}$ into $U_M\bigcup W_M\bigcup (W\backslash W_M)\bigcup (U\backslash U_M)$ as shown in Figure 1. For all $x\in W\backslash W_M$ (rep. $y\in U_M$, $z\in W_M$, $w\in U\backslash U_M$), by computing immediately, we have

$$\begin{array}{ccc}\hfill \sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{y\in U_M}}\frac{1}{r_{G^{\prime }}(x,y)}& =& \sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{y\in U_M}}\frac{1}{r_{G^{″}}(x,y)}=\frac{n_2^2{q}^2}{n_2+q-1}.\hfill \\ \hfill \sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{z\in W_M}}\frac{1}{r_{G^{\prime }}(x,z)}& =& \sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{z\in W_M}}\frac{1}{r_{G^{″}}(x,z)}=\frac{n_2{q}^2}{2}+\frac{n_2^{2}q}{2}.\hfill \\ \hfill \sum _{\genfrac{}{}{0pt}{}{y\in U_M}{z\in W_M}}\frac{1}{r_{G^{\prime }}(y,z)}& =& \sum _{\genfrac{}{}{0pt}{}{y\in U_M}{z\in W_M}}\frac{1}{r_{G^{″}}(y,z)}=\frac{q^4}{2q-1}.\hfill \\ \hfill \sum _{\genfrac{}{}{0pt}{}{z\in W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{\prime }}(z,w)}& =& \frac{n_1{q}^2}{2}+\frac{q{n}_1^2}{2}.\sum _{\genfrac{}{}{0pt}{}{z\in W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{″}}(z,w)}=\frac{n_2^2{q}^2}{n_2+q-1}.\hfill \\ \hfill \sum _{\genfrac{}{}{0pt}{}{y\in U_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{\prime }}(y,w)}& =& \frac{n_1^2{q}^2}{n_1+q-1}.\sum _{\genfrac{}{}{0pt}{}{y\in U_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{″}}(y,w)}=\frac{n_2{q}^2}{2}+\frac{q{n}_2^2}{2}.\hfill \end{array}$$

For $x\in W\backslash W_M$ and $w\in U\backslash U_M$, the resistance distance between two vertices x and w is

$$r_{G^{\prime }}(x,w)=1+1+\frac{2q-1}{q^2}=\frac{2q^2+2q-1}{q^2}.$$

Then, we have

$$\begin{array}{ccc}\hfill \sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{\prime }}(x,w)}& =& \frac{q^2{n}_1{n}_2}{2q^2+2q-1}.\sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{″}}(x,w)}=\frac{n_1{n}_{2}q}{2}.\hfill \end{array}$$

This gives

$$\begin{array}{ccc}\hfill RH\left(G^{″}\right)-RH\left(G^{\prime }\right)& =& (\sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{″}}(x,w)}+\sum _{\genfrac{}{}{0pt}{}{y\in U_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{″}}(y,w)}+\sum _{\genfrac{}{}{0pt}{}{z\in W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{″}}(z,w)})\hfill \\ \hfill & -& (\sum _{\genfrac{}{}{0pt}{}{x\in W\backslash W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{\prime }}(x,w)}+\sum _{\genfrac{}{}{0pt}{}{y\in U_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{\prime }}(y,w)}+\sum _{\genfrac{}{}{0pt}{}{z\in W_M}{w\in U\backslash U_M}}\frac{1}{r_{G^{\prime }}(z,w)}).\hfill \\ \hfill & =& (\frac{n_1{n}_{2}q}{2}+\frac{n_2^2{q}^2}{n_2+q-1}+\frac{n_2{q}^2+n_2^{2}q}{2})\hfill \\ \hfill & -& (\frac{q^2{n}_1{n}_2}{2q^2+2q-1}+\frac{n_1^2{q}^2}{n_1+q-1}+\frac{n_1{q}^2+n_1^{2}q}{2}).\hfill \\ \hfill & =& n_1{n}_2\frac{2q^3-q}{2(2q^2+2q-1)}+\frac{q^2}{2}(n_2-n_1)+\frac{q}{2}(n_2^2-n_1^2)\hfill \\ \hfill & +& \frac{n_2^2{q}^2}{n_2+q-1}-\frac{n_1^2{q}^2}{n_1+q-1}.\hfill \end{array}$$

where $n_2-n_1>0$, $n_2^2-n_1^2>0$ for $n_2>n_1$. $\frac{2q^3-q}{2(2q^2+2q-1)}>0$ for $q\ge 1$. By Lemma 4, the function $f\left(x\right)=\frac{x^2{q}^2}{x+q-1}$ for $q>1$ and $x>q$ is strictly increasing. Thus when $n_2\ge n_1>q$, we have

$$\frac{n_2^2{q}^2}{n_2+q-1}-\frac{n_1^2{q}^2}{n_1+q-1}>0.$$

According to the above analysis, we have $RH\left(G^{″}\right)-RH\left(G^{\prime }\right)>0$, thus

$$RH\left(G^{″}\right)>RH\left(G^{\prime }\right).$$

This completes the proof. ◻

4. Graphs with Given Vertex Bipartiteness

In this section, we described the extremal graph with a given vertex bipartiteness for Resistance–Harary index. Let $G_1$ and $G_2$ be the graphs where any two vertices do not intersect. We obtain the joint graph of $G_1$ and $G_2$ through the correlation of every vertex of graph $G_1$ with every vertex of graph $G_2$, denoted it by $G_1\vee G_2$. The vertex bipartiteness of a graph G is the minimum number of vertices removed makes the graph G a bipartite graph, which is denoted by $v_b\left(G\right)$, see [17]. Let ${\mathrm{G}}_{n,\delta }$ be the set of the graphs with n vertices and $v_b\left(G\right)\le \delta$, where $\delta$ is the positive integer that does not exceed $n-2$.

Lemma 5.

Let G be the graph in ${\mathrm{G}}_{n,\delta }$. There is a pair of positive integers s and t that satisfies $s+t=n-\delta$, we have $RH\left(G\right)\le RH\left(G^{*}\right)$ for all graphs $G\in {\mathrm{G}}_{n,\delta }$, and the equality holds if and only if $G^{*}\cong K_{\delta }\vee K_{s,t}$.

Proof. 

By Lemma 2, we know that $RH$ is a topological index whose value increases with the number of edges. Let $G^{*}\in {\mathrm{G}}_{n,\delta }$ be the graph with the largest $RH$ index value, that is to say, $RH\left(G^{*}\right)\ge RH\left(G\right)$ for all graphs $G\in {\mathrm{G}}_{n,\delta }$. Since $G^{*}\in {\mathrm{G}}_{n,\delta }$, there are $v_1,v_2,\cdots ,v_k\in V\left(G^{*}\right)$ ($k\le \delta$) such that $G^{*}-\{v_1,v_2,\cdots ,v_k\}$ is a bipartite graph, let $(X,Y)$ be its vertex sets, and $\left|X\right|=s$ and $\left|Y\right|=t$. Thus, $s+t=n-k$. If $G^{*}-\{v_1,v_2,\cdots ,v_k\}\ne K_{s,t}$, then there exists two vertices u, v that are not adjacent and $u\in X$, $v\in Y$. We get another graph $G^{*}+e\in {\mathrm{G}}_{n,\delta }$ by getting a new edge $e=uv$, then $RH(G^{*}+e)>RH\left(G^{*}\right)$, and we get the contradiction, so $G^{*}-\{v_1,v_2,\cdots ,v_k\}=K_{s,t}$. In addition, if there are two vertices that are not adjacent to each other and $u,v\in \{v_1,v_2,\cdots ,v_k\}$, then we get a new graph $G^{*}+uv\in {\mathrm{G}}_{n,\delta }$, by adding a new edge $uv$ into $G^{*}$, then $RH(G^{*}+uv)>RH\left(G^{*}\right)$, again, a contradiction. This suggests that the subgraph induced by $\{v_1,v_2,\cdots ,v_k\}$ is $K_k$, so $G^{*}\cong K_k\vee K_{s,t}$. At last, we prove that $k=\delta$. To the contrary, assume that $\left|X\right|=s\ge 2$ or $\left|Y\right|=t\ge 2$. Naturally, we set $t\ge 2$. Pick a vertex v from Y, and add the edges $v{v}_i$ to $K_k\vee K_{s,t}$, where $v_i\in \{v_1,v_2,\cdots ,v_k\}$, the resulting graph is $K_{k+1}\vee K_{s,t-1}\in {\mathrm{G}}_{n,\delta }$, and it has $t-1\ge 1$ edges more than graph $G^{*}$, implying that $RH(K_{k+1}\vee K_{s,t-1})>RH(K_k\vee K_{s,t})=RH\left(G^{*}\right)$, which is a contradiction. Therefore, $k=\delta$ and $G^{*}\cong K_{\delta }\vee K_{s,t}$. Complete the proof of the theorem. ◻

Lemma 6.

Let $G\cong K_{\delta }\vee K_{s,t}$ and $G^{{}^{\prime }}\cong K_{\delta }\vee K_{s+1,t-1}$. If $s\le t-2$, then $RH\left(G^{{}^{\prime }}\right)>RH\left(G\right)$.

Proof. 

By the definition of the $RH$ index and by Lemma 1, we have

$$\begin{array}{ccc}\hfill RH\left(G\right)& =& RH(K_{\delta }\vee K_{s,t})\hfill \\ \hfill & =& RH\left(K_{s,t}\right)+RH\left(K_{\delta }\right)+\sum _{\genfrac{}{}{0pt}{}{x\in V\left(K_{s,t}\right)}{y\in V\left(K_{\delta }\right)}}\frac{1}{r_G(x,y)},\hfill \\ \hfill & =& RH\left(K_{s,t}\right)+RH\left(K_{\delta }\right)\hfill \\ \hfill & +& s\delta (1+\frac{t(\delta -1))}{2}+\frac{(s-1)t}{3})+t\delta (1+\frac{s(\delta -1)}{2}+\frac{(t-1)s}{3}),\hfill \\ \hfill & =& \frac{st(4st+{(s+t)}^2-3(s+t)+2)}{4(s+t-1)}+\frac{{\delta }^2(\delta -1)}{8},\hfill \\ \hfill & +& \frac{\delta (6s+6t+6st(\delta -1)+2st(s+t-2\left)\right)}{6},\hfill \end{array}$$

where $M={(s+t)}^2-3(s+t)+2$. We have

$$\begin{array}{ccc}\hfill RH\left(G^{{}^{\prime }}\right)& =& RH(K_{\delta }\vee K_{s+1,t-1})\hfill \\ \hfill & =& RH\left(K_{s+1,t-1}\right)+RH\left(K_{\delta }\right)+\sum _{\genfrac{}{}{0pt}{}{x\in V\left(K_{s+1,t-1}\right)}{y\in V\left(K_{\delta }\right)}}\frac{1}{r_G(x,y)},\hfill \\ \hfill & =& \frac{4{(s+1)}^2{(t-1)}^2+M(st+t-s-1)}{4(s+t-1)}+\frac{{\delta }^2(\delta -1)}{8},\hfill \\ \hfill & +& \frac{\delta (6s+6t+6(s+1\left)\right(t-1\left)\right(\delta -1)+2(s+1\left)\right(t-1\left)\right(s+t-2\left)\right)}{6}.\hfill \end{array}$$

where $M={(s+t)}^2-3(s+t)+2$. So

$$\begin{array}{ccc}\hfill RH\left(G^{{}^{\prime }}\right)-RH\left(G\right)& =& \frac{4(t-s-1)(2st+t-s-1)+M(t-s-1)}{4(s+t-1)},\hfill \\ \hfill & +& \frac{\delta (t-s-1)\left(6\right(\delta -1)+2(s+t-2\left)\right)}{6},\hfill \\ \hfill & >& 0.\hfill \end{array}$$

where $M={(s+t)}^2-3(s+t)+2$. Then $RH\left(G^{{}^{\prime }}\right)>RH\left(G\right).$ This completes the proof. ◻

Next, we describe the graphs with extremal Resistance–Harary index values in the graph with given vertex bipartiteness. The following conclusion is easy to deduce by applying Lemmas 2, 5, and 6.

Theorem 4.

Let G be the graph of ${\mathrm{G}}_{n,\delta }$. Where $1\le \delta \le n-2$, then

(a) If $n-m$ is even, then $RH\left(G^{*}\right)\ge RH\left(G\right)$ holds, where $G^{*}\cong K_{\delta }\vee K_{\frac{n-\delta }{2},\frac{n-\delta }{2}}$.

(b) If $n-m$ is odd, then $RH\left(G^{*}\right)\ge RH\left(G\right)$ holds, where $G^{*}\cong K_{\delta }\vee K_{\lfloor \frac{n-\delta }{2}\rfloor ,\lceil \frac{n-\delta +1}{2}\rceil }$.

5. Bipartite Graph with a Given Cut Edges

In this section, we determine bipartite graph given cut edges with maximum Resistance–Harary index.

Lemma 7.

$G_1$ and $G_2$ are connected graphs whose vertices do not intersect, assume that $u\in G_1$ and $v\in G_2$. We connect u and v to get G, and if we identified two vertices u with v in G, we get graph $G^{{}^{\prime }}$. Let the new vertex be w, which is adjacent to a pendant vertex $w_0$ (see Figure 2). Then $RH\left(G^{{}^{\prime }}\right)>RH\left(G\right)$.

Proof. 

By Lemma 1 and the definition of $RH$ index, we have

$$\begin{array}{ccc}\hfill RH\left(G\right)& =& \sum _{i=1}^{2}RH\left(G_i\right)+\sum _{x\in V\left(G_1\right)}\frac{1}{r_{G_1}(x,u)+1}+1\hfill \\ \hfill & +& \sum _{y\in V\left(G_2\right)}\frac{1}{r_{G_2}(v,y)+1}+\sum _{\genfrac{}{}{0pt}{}{x\in V\left(G_1\right),}{y\in V\left(G_2\right)}}\frac{1}{r_{G_1}(x,u)+r_{G_2}(y,v)+1}.\hfill \end{array}$$

$$\begin{array}{ccc}\hfill RH(G^{{}^{\prime }})& =& \sum _{i=1}^{2}RH\left(G_i\right)+\sum _{x\in V\left(G_1\right)}\frac{1}{r_{G_1}(x,u)+1}+1\hfill \\ \hfill & +& \sum _{y\in V\left(G_2\right)}\frac{1}{r_{G_2}(v,y)+1}+\sum _{\genfrac{}{}{0pt}{}{x\in V\left(G_1\right),}{y\in V\left(G_2\right)}}\frac{1}{r_{G_1}(x,u)+r_{G_2}(y,v)}.\hfill \end{array}$$

$$\begin{array}{ccc}\hfill RH(G^{{}^{\prime }})-RH\left(G\right)& =& \sum _{\genfrac{}{}{0pt}{}{x\in V\left(G_1\right),}{y\in V\left(G_2\right)}}(\frac{1}{r_{G_1}(x,u)+r_{G_2}(y,v)}-\frac{1}{r_{G_1}(x,u)+r_{G_2}(y,v)+1})\hfill \\ \hfill & >& 0.\hfill \end{array}$$

Then $RH\left(G^{{}^{\prime }}\right)>RH\left(G\right).$ This completes the proof. ◻

Lemma 8

([13]). Let G be a graph from a connect graph $G_0$ by attaching some pendant vertices. If u and v are two vertices in graph $G_0$, pendant vertices $u_1,u_2,\cdots ,u_a$ are attached to the vertex u and b pendant vertices $v_1,v_2,\cdots ,v_b$ are attached to the vertex v. Let $G^{{}^{\prime }}=G-\{v{v}_1,v{v}_2,\cdots ,v{v}_b\}+\{u{v}_1,u{v}_2,\cdots ,u{v}_b\}$ and $G^{″}=G-\{u{u}_1,u{u}_2,\cdots ,u{u}_a\}+\{v{u}_1,v{u}_2,\cdots ,v{u}_a\}$. Then $RH\left(G^{{}^{\prime }}\right)>RH\left(G\right)$ or $RH\left(G^{″}\right)>RH\left(G\right)$.

Lemma 9.

For bipartite graph $K_{r,s}^k$ with $r>s+2$ and $k,s\ge 1$ (see Figure 3). One has $RH\left(K_{r,s}^k\right)<RH(K_{r-1,s+1}^k)$.

Proof. 

By Lemmas 1 and direct calculations, we can get the value of $RH$ of $K_{r,s}^k$.

$$\begin{array}{ccc}\hfill RH\left(K_{r,s}^k\right)& =& RH\left(S_k\right)+RH\left(K_{r,s}\right)+\sum _{\genfrac{}{}{0pt}{}{x\in V\left(S_k\right)}{y\in V\left(K_{r,s}\right)}}\frac{1}{r_G(x,y)}\hfill \\ \hfill & =& \frac{k^2+3k}{4}+\frac{rs(4rs+{(r+s)}^2-3(r+s)+2)}{4(r+s-1)}+k[\frac{rs+2}{r+2}+\frac{s{r}^2}{rs+r+s-1}].\hfill \end{array}$$

Let $f(r,s)=\frac{rs(4rs+{(r+s)}^2-3(r+s)+2)}{4(r+s-1)}$. Then we know from the proof of Theorem 1, $f(r-1,s+1)>f(r,s)$. Similarly, let $g(r,s)=\frac{rs+2}{r+2}+\frac{s{r}^2}{rs+r+s-1}$, by comparison, we have $g(r-1,s+1)-g(r,s)>0$. Thus, we have $RH\left(K_{r,s}^k\right)<RH(K_{r-1,s+1}^k).$ This completes the proof. ◻

By Lemma 9, it is straightforward to see that

Corollary 2.

Let ${\mathcal{G}}_n^k$ be the bipartite graphs of order n with k cut edges obtained by identifying the center of $K_{k+1}$ order star graph and one vertex of a complete graph with $n-k$ vertices. For $G\in {\mathcal{G}}_n^k$, we have $RH\left(G\right)\le RH(K_{\left[\frac{n-k}{2}\right]\lceil \frac{n-k}{2}\rceil }^k)$, and equality is attained if and only if $G\cong K_{\left[\frac{n-k}{2}\right]\lceil \frac{n-k}{2}\rceil }^k$.

Let ${\mathcal{B}}_n^k$ be the set of connected bipartite graphs with n order and k cut edges. For $k=0$, from Theorem 1, then the graph with maximum $RH$ index is isomorphic to graph $K_{\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil }$. For $k=n-1$, the bipartite graph is a tree, so the Resistance distance and distance between the vertices in the tree are equal, that is, the Resistance–Harary index in the tree was the same as the $Harary$ index. So the maximum Resistance–Harary index is obtained uniquely at $S_n$.

Next, we focus on the case $1\le k\le n-4$.

Theorem 5.

In all connected bipartite graphs with n order and k cut edges, where $1\le k\le n-4$, the maximum Resistance–Harary index is founded at $K_{\lfloor \frac{n-k}{2}\rfloor \lceil \frac{n-k}{2}\rceil }^k$.

Proof. 

Let $G_0$ be the graph having the maximum $RH$ index value in ${\mathcal{B}}_n^k$ and $E_1$ be the set of cut edges of $G_0$. Where $G_0$ and $G_0-E_1$ are bipartite graphs, then by Lemma 2, we can know that each component of $G_0-E_1$ is a complete bipartite graph. In addition, by Lemma 7, every edge of $E_1$ must be pendant edges. Hence, $G_0$ must be the graph constructed from $K_{m,n-m-k}$ by hanging k pendant edges. Finally, by Lemma 8, all these pendant edges in $G_0$ must be attached to one common vertex. That is to say, $G_0$ must be one of the graph ${\mathcal{G}}_n^k$, furthermore, by Corollary 2, we get that $G_0\cong K_{\lfloor \frac{n-k}{2}\rfloor \lceil \frac{n-k}{2}\rceil }^k$. This completes the proof. ◻

6. Discussion

Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena. In chemical graph theory, vertices represent atoms and edges represent the connections between atoms. The topological exponent of a graph is a function defined on a (molecular) graph regardless of the labeling of its vertices. The Resistance–Harary index is a topological descriptor that has been correlated with the relationship between structure and performance and between structure and activity molecular descriptors. To correlate with electrical network theory and real analysis, the Resistance–Harary index has much better predictive power than that of the global cyclicity index.

7. Conclusions

In this paper, we first present a structural of the extremal graphs for Resistance–Harary index over all bipartite graphs with n vertices, then characterize the extremal graphs given vertex bipartiteness on the $RH$ index. Moreover, we optimize the extremal structure of bipartite graphs with given cut edges and bipartite graphs with given matching numbers. Along this line, some other interesting extremal problems on bipartite graphs with given parameters are valuable to be considered. In the future we can also characterize extremal bipartite graphs with fixed diameter on the Resistance–Harary index.