Residual Closeness of Graphs with Given Parameters

Abstract

Robustness of the network topology is a key aspect in the design of computer networks. Residual closeness is a new graph-theoretic concept defined as a measure of network robustness due to the failure of individual vertices. We identify those graphs with maximum residual closeness among connected graphs with fixed connectivity, edge connectivity and bipartiteness, respectively.

1 Introduction

A network is usually represented by an undirected simple graph where vertices represent processors and edges represent links between processors. The measures of network vulnerability are usually graph invariants that measure how a deletion of one or more network elements (vertices or edges) changes properties of the network. In the literature, some graph invariants such as connectivity [1], toughness [2], scattering number [3] and binding number [4] have been used for this purpose, and each of them has its own strengths and weaknesses when it comes to understanding a graph. Dangalchev [5] proposed a new measure for network vulnerability called residual closeness, which utilizes closeness received after the removal of a vertex and its links. The aim of residual closeness is to measure the vulnerability even when the removal of the vertices does not disconnect the graph. Dangalchev explained the advantage of residual closeness as a measure for the graph vulnerability and noted that there are examples to show that the residual closeness can reflect the vulnerability of graphs more sensitive than or independent of the other parameters in the existing literature.

Let G be a graph with vertex set V(G) and edge (link) set E(G). For vertices u, v of G, the distance between u and v in G is the length of a shortest path between u and v in G, denoted by $d_G(u,v)$. Note that $d_G(u,v)=+\infty$ if there is no path connecting u and v (i.e., u and v lie in different components). For an overview of results concerning the distances in graphs, see the monograph [6]. Following [5], for a vertex u of the graph G, the closeness of u in G is defined as $C_G(u)=\sum _{v\in V(G)\setminus \{u\}}2^{-d_G(u,v)}$, which is also known as a decay centrality of u in G [7]. The closeness of a graph G is defined as

$$\begin{aligned} C(G)=\sum _{u\in V(G)}C_G(u)=\sum _{u\in V(G)}\sum _{v\in V(G)\setminus \{u\}}2^{-d_G(u,v)}. \end{aligned}$$

The residual closeness (or vertex residual closeness) of a non-trivial graph G is defined as [5]

$$\begin{aligned} R(G)=\min \{C(G-u): u\in V(G)\}, \end{aligned}$$

where $G-u$ is the graph obtained from G by deleting vertex u (and its incident edges).

The computational aspect of the residual closeness has received much attention. For example, Dangalchev established some formulas for easy calculation of the residual closeness and put forward a generalized version of the residual closeness in [8], and he also expressed the residual closeness of thorn graphs as a function of the closeness and the residual closeness of the original graphs in [9]; Aytac and coauthors computed the residual closeness of gear graphs and friendship graphs in [10], cycle related graphs, including fans, k-pyramid graphs, wheels, n-gon books and shadow graphs of cycles in [11], regular caterpillars in [12], helm and sunflower graphs in [13], and the graphs formed by unary and binary graph operations in [14].

In the extremal aspect of the residual closeness, the following problems are considered. Let $\mathbb {G}$ be a family of graphs. It is of importance to determine

$$\begin{aligned} \min \{R(G): G\in \mathbb {G}\} \text{ and } \max \{R(G): G\in \mathbb {G}\}, \end{aligned}$$

and characterize the graphs in $\mathbb {G}$ for which the residual closeness attains the minimum and maximum over $\mathbb {G}$. Rupnik Poklukar and Žerovnik determined in [15] the extremal graphs that minimize or maximize the closeness C(G) among all graphs and among several subclasses of graphs including trees and cacti. Recently, Zhou et al. [16] have identified the graphs that minimize or maximize the residual closeness over some families of graphs, including the families of bipartite graphs and trees with fixed parameters.

A vertex cut of a connected graph G that is not complete is a set S of vertices such that the graph obtained from G by removing the vertices in S (and the incident edges) is disconnected. The connectivity $\kappa (G)$ of a graph G is defined as the minimum cardinality of vertex cuts of G if G is not complete, and $\kappa (G)=n-1$ otherwise, where n is the order of G, see [17]. It is evident that $\kappa (G)$ is the minimum number of vertices whose removal results in a disconnected or trivial graph.

For a graph G with $\varnothing \ne S, T\subset V(G)$ with $S\cap T=\varnothing$, denote by [S, T] the set of edges of G between S and T. An edge cut of a graph G is a subset of edges of G of the form $[S, V(G)\setminus S]$, where $\varnothing \ne S\subset V(G)$. The edge connectivity $\lambda (G)$ of a non-trivial connected graph G is defined as the minimum cardinality of edge cuts of G and if G is trivial, it is defined as 0, see [17].

Recall that a graph is bipartite if it is possible to partition its vertices into two parts such that there are no edges with both endpoints in the same part. Lewis and Yannakakis [18] investigated the problem: For a fixed graph property $\Pi$, what is the minimum number of vertices which must be deleted from a given graph so that the resulting subgraph has property $\Pi$? If $\Pi$ is bipartite, the minimum number of vertices whose deletion from G yields a bipartite graph is called the (vertex) bipartiteness [19] (or bipartite vertex frustration [20]) of G.

To understand the relationship between the residual closeness and the structural properties, in this paper, we consider to maximize the residual closeness in the families of graphs with fixed connectivity, edge connectivity and bipartiteness, respectively, and the extremal graphs are completely characterized.

2 Preliminaries

For a proper subset $V_1$ of vertices of a graph G, $G-V_1$ denotes the subgraph of G obtained by deleting all vertices in $V_1$ (and the incident edges) from G, and in particular, if $V_1=\{u\}$, then we write $G-u$ for $G-\{u\}$. For a subset $E_1$ of edges of a graph G, $G-E_1$ denotes the subgraph obtained from G by deleting all edges in $E_1$, and in particular, if $E_1=\{e\}$, then we write $G-e$ for $G-\{e\}$.

For vertex disjoint graphs $G_1$ and $G_2$, the union of $G_1$ and $G_2$, denoted by $G_1\cup G_2$, is the graph with vertex set $V(G_1) \cup V(G_2)$ and the edge set $E(G_1)\cup E(G_2)$. The join of $G_1$ and $G_2$, denoted by $G_1\vee G_2$, is the graph obtained from $G_1\cup G_2$ by adding all edges between $V(G_1)$ and $V(G_2)$.

Denote by $K_n$ the n-vertex complete graph and $K_{r,s}$ the complete bipartite graph with part sizes r and s.

The following lemma will be frequently used in the proofs.

Lemma 1

[5, 16] Let G be a graph with $uv\in E(G)$. Then $R(G-uv)\leqslant R(G)$ for any $uv\in E(G)$.

We also need the following lemmas.

Lemma 2

[17] Let G be a connected graph G with minimum degree $\delta (G)$. Then, $\kappa (G)\leqslant \lambda (G)\leqslant \delta (G)$.

Lemma 3

[16] Let G be an n-vertex bipartite graph with $n\geqslant 4$. Then,

$$\begin{aligned} R(G)\leqslant \frac{(n-1)(n-2)}{4}+\frac{1}{2}\left( \left\lfloor \frac{n}{2}\right\rfloor -1\right) \left\lceil \frac{n}{2}\right\rceil \end{aligned}$$

with equality if and only if $G\cong K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$.

3 Residual Closeness and Connectivity

In this section, we determine all connected graphs with fixed number of vertices and connectivity having maximum residual closeness.

Lemma 4

Suppose that $G=K_\kappa \vee (K_r\cup K_s)$ with $\kappa \geqslant 1$ and $1\leqslant r\leqslant s$. Then,

$$\begin{aligned} R(G)={\left\{ \begin{array}{ll} \frac{r(r-1)}{2}+\frac{s(s-1)}{2}, &{} \text{ if } \kappa =1,\\ \frac{(\kappa -1)(\kappa -2)}{2}+\frac{r(r-1)}{2}+\frac{s(s-1)}{2}+(\kappa -1) (r+s)+\frac{rs}{2}, &{} \text{ if } \kappa \geqslant 2. \end{array}\right. } \end{aligned}$$

Proof

Let $G=K_\kappa \vee (K_r\cup K_s)$. Let u be a vertex of G in $K_\kappa$, v a vertex of G in $K_r$ and w a vertex of G in $K_s$. For positive integers a, b and c, it is evident that

$$\begin{aligned} C(K_a\vee (K_b\cup K_c))&=C(K_a)+C(K_b)+C(K_c)+2\left( \frac{a(b+c)}{2}+\frac{bc}{4}\right) \\&=\frac{a(a-1)}{2}+\frac{b(b-1)}{2}+\frac{c(c-1)}{2}+a (b+c)+\frac{bc}{2}. \end{aligned}$$

Case 1 $\kappa =1$.

It is easily seen that

$$\begin{aligned} C(G-u)=C(K_r)+C(K_s)=\frac{r(r-1)}{2}+\frac{s(s-1)}{2}. \end{aligned}$$

Note that $G-v=K_1\vee (K_{r-1}\cup K_s)$, where $K_0\cup K_s=K_s$ if $r=1$. Then,

$$\begin{aligned} C(G-v)=\frac{(r-1)(r-2)}{2}+\frac{s(s-1)}{2}+r+s-1+\frac{(r-1)s}{2}. \end{aligned}$$

Similarly,

$$\begin{aligned} C(G-w)=\frac{r(r-1)}{2}+\frac{(s-1)(s-2)}{2}+r+s-1+\frac{r(s-1)}{2}. \end{aligned}$$

Thus,

$$\begin{aligned} C(G-v)-C(G-w)=\frac{s-r}{2}\geqslant 0 \end{aligned}$$

and

$$\begin{aligned} C(G-w)-C(G-u)=r+\frac{r(s-1)}{2}>0. \end{aligned}$$

It then follows that $C(G-u)<C(G-w)\leqslant C(G-v)$. Therefore, $R(G)=C(G-u)=\frac{r(r-1)}{2}+\frac{s(s-1)}{2}$.

Case 2 $\kappa \geqslant 2$.

Note that

$$\begin{aligned} C(G-u)=\frac{(\kappa -1)(\kappa -2)}{2}+\frac{r(r-1)}{2}+\frac{s(s-1)}{2}+(\kappa -1) (r+s)+\frac{rs}{2}, \end{aligned}$$

$$\begin{aligned} C(G-v)=\frac{\kappa (\kappa -1)}{2}+\frac{(r-1)(r-2)}{2}+\frac{s(s-1)}{2}+\kappa (r+s-1)+\frac{(r-1)s}{2} \end{aligned}$$

and

$$\begin{aligned} C(G-w)=\frac{\kappa (\kappa -1)}{2}+\frac{r(r-1)}{2}+\frac{(s-1)(s-2)}{2}+\kappa (r+s-1)+\frac{r(s-1)}{2}. \end{aligned}$$

Then

$$\begin{aligned} C(G-v)-C(G-w)=\frac{s-r}{2}\geqslant 0 \end{aligned}$$

and

$$\begin{aligned} C(G-w)-C(G-u)=\frac{r}{2}>0. \end{aligned}$$

So $C(G-u)<C(G-w)\leqslant C(G-v)$. Thus, $R(G)=C(G-u)=\frac{(\kappa -1)(\kappa -2)}{2}+\frac{r(r-1)}{2}+\frac{s(s-1)}{2}+(\kappa -1) (r+s)+\frac{rs}{2}$.

For integers $s\geqslant 2$ and $\ell$ with $1\leqslant \ell \leqslant s-1$, denote by $H_{s+2,\ell }$ the graph obtained from $K_1\vee (K_1\cup K_s)$ by deleting $\ell$ edges joining the vertex of degree $s+1$ and the vertices of degree s. Denote by v the vertex of degree one in $K_1\vee (K_1\cup K_s)$.

Lemma 5

Suppose that $s\geqslant 3$ and $\ell \geqslant 1$. Then $R(H_{s+2,\ell }) = \frac{s(s-1)}{2}$ if and only if $\ell \leqslant \min \{s-2, \lfloor \frac{2(s+1)}{3}\rfloor \}$.

Proof

Let u be the vertex of degree $s-\ell +1$ that is adjacent to vertex v in $H_{s+2, \ell }$. Let $W=V(H_{s+2, \ell })\setminus \{u,v\}$. Let $H_{s+2,\ell }=K_1\vee (K_1\cup K_s)-E$ with E being a set of $\ell$ edges joining u and vertices in W.

Suppose first that $\ell \leqslant \min \bigg \{s-2, \lfloor \frac{2(s+1)}{3}\rfloor \bigg \}$. Then

$$\begin{aligned} C(H_{s+2, \ell }-u)=C(K_s)=\frac{s(s-1)}{2} \end{aligned}$$

and

$$\begin{aligned} C(H_{s+2, \ell }-v)=\frac{s(s-1)}{2}+s-\frac{\ell }{2}. \end{aligned}$$

Let $w_1, w_2\in W$ be vertices of $H_{s+2, \ell }$ with degrees $s-1$ and s, respectively. Then,

$$\begin{aligned} C(H_{s+2,\ell }-w_1)=\frac{(s-1)(s-2)}{2}+1+s-1-\frac{\ell -1}{2}+\frac{1}{2}\left( s-1-\frac{\ell -1}{2}\right) , \end{aligned}$$

where vertex pairs from $\{u\}\times W$ contribute $s-1-\frac{\ell -1}{2}$ to $C(H_{s+2, \ell }-w_1)$ and vertex pairs from $\{v\}\times W$ contribute $\frac{1}{2}\left( s-1-\frac{\ell -1}{2}\right)$ to $C(H_{s+2, \ell }-w_1)$. Similarly, since $\ell \leqslant s-2$, one has

$$\begin{aligned} C(H_{s+2, \ell }-w_2)=\frac{(s-1)(s-2)}{2}+1+s-1-\frac{\ell }{2}+\frac{1}{2}\left( s-1-\frac{\ell }{2}\right) . \end{aligned}$$

Then

$$\begin{aligned} C(H_{s+2, \ell }-v)-C(H_{s+2, \ell }-w_1)=\frac{2s+\ell -5}{4}>0, \end{aligned}$$

$$\begin{aligned} C(H_{s+2, \ell }-w_1)-C(H_{s+2, \ell }-w_2)=\frac{3}{4}>0 \end{aligned}$$

and

$$\begin{aligned} C(H_{s+2, \ell }-w_2)-C(H_{s+2, \ell }-u)=\frac{2(s+1)-3\ell }{4}\geqslant 0 \end{aligned}$$

as $\ell \leqslant \lfloor \frac{2(s+1)}{3}\rfloor$. So $C(H_{s+2, \ell }-u)\leqslant C(H_{s+2, \ell }-w_2)< C(H_{s+2, \ell }-w_1)<C(H_{s+2, \ell }-v)$. Thus

$$\begin{aligned} R(H_{s+2, \ell })= C(H_{s+2, \ell }-u)=\frac{s(s-1)}{2}. \end{aligned}$$

Conversely, suppose that $R(H_{s+2,\ell }) = \frac{s(s-1)}{2}$.

If $\ell = s-1$, then there is only one vertex w in W that is not incident to any edge in E, and for w, we have

$$\begin{aligned} C( H_{s+2,\ell }-w) = \frac{(s-1)(s-2)}{2}+1, \end{aligned}$$

so $R(H_{s+2,\ell })\leqslant C(H_{s+2,\ell }-w) < \frac{s(s-1)}{2}$, a contradiction.

If $\ell >\frac{2(s+1)}{3}$, then, as $\ell \leqslant s-2$, we can choose a vertex, say $w_2$, in W that is not incident to any edge in E, and as above, we have

$$\begin{aligned} C(H_{s+2,\ell }-w_2)&= \frac{(s-1)(s-2)}{2}+1+s-1-\frac{\ell }{2}+\frac{1}{2}\left( s-1-\frac{\ell }{2}\right) \\&=\frac{s^2}{2}-\frac{3\ell -2}{4}, \end{aligned}$$

and thus $R(H_{s+2,\ell })\leqslant C(H_{s+2,\ell }-w_2) < \frac{s(s-1)}{2}$, also a contradiction.

It follows that $\ell \leqslant \min \{s-2, \lfloor \frac{2(s+1)}{3}\rfloor \}$.

Note that the complete graph $K_n$ is the unique connected graph on n vertices with connectivity $n-1$. Let $2K_1$ be the empty graph on two vertices.

Theorem 1

Let G be a connected graph on n vertices with connectivity $\kappa$, where $1\leqslant \kappa \leqslant n-2$. Then,

$$\begin{aligned} R(G)\leqslant {\left\{ \begin{array}{ll} \frac{(n-2)(n-3)}{2}, &{} \text{ if } \kappa =1,\\ \frac{(n-1)(n-3)+\kappa }{2}, &{} \text{ if } \kappa \geqslant 2 \end{array}\right. } \end{aligned}$$

with equality if and only if G is isomorphic to one of the following graphs:

• (i) $K_1\vee (K_1\cup K_{n-2})$, or $H_{4,1}$, or $H_{n,\ell }$ with $n\geqslant 5$ and $\ell =1, \cdots , \min \{n-4, \lfloor \frac{2(n-1)}{3}\rfloor \}$, if $\kappa =1$;

• (ii) $K_2\vee (K_1\cup K_{n-3})$ or $2K_1\vee (K_1\cup K_{n-3})$, if $\kappa =2$;

• (iii) $K_{\kappa }\vee (K_1\cup K_{n-\kappa -1})$, if $\kappa \geqslant 3$.

Proof

Suppose that G is a connected graph on n vertices with connectivity $\kappa$ that maximizes the residual closeness.

Let S be a vertex cut of G with $\kappa$ vertices. Then the graph $G-S$ is disconnected. Assume that $G_1$ is a component of $G-S$. Let $G_2=G-S-V(G_1)$. Then $G-S=G_1\cup G_2$. Denote by r and s the order of $G_1$ and $G_2$, respectively. Then $r+s=n-\kappa$. Assume that $r\leqslant s$. So $G\subseteq K_\kappa \vee (K_r\cup K_s)$. By the choice of G and Lemmas 1 and 4, we have

$$\begin{aligned} R(G)=R(K_\kappa \vee (K_r\cup K_s))=F(\kappa , r,s), \end{aligned}$$

(1)

where

$$\begin{aligned} F(\kappa , r, s):= {\left\{ \begin{array}{ll} \frac{r(r-1)}{2}+\frac{s(s-1)}{2},&{} \text{ if } \kappa =1\text{, }\\ \frac{(\kappa -1)(\kappa -2)}{2}+\frac{r(r-1)}{2}+\frac{s(s-1)}{2}+(\kappa -1) (r+s)+\frac{rs}{2},&{} \text{ if } \kappa \geqslant 2\text{. } \end{array}\right. } \end{aligned}$$

Note that

$$\begin{aligned} F(\kappa , r, s),&={\left\{ \begin{array}{ll} \frac{r^2+s^2-(n-1)}{2},&{} \text{ if } \kappa =1\\ \frac{(n-\kappa )(2\kappa -3)}{2}+\frac{(\kappa -1)(\kappa -2)}{2}+\frac{r^2+s^2+rs}{2}, &{} \text{ if } \kappa \geqslant 2 \end{array}\right. } \\&={\left\{ \begin{array}{ll} \frac{(n-1)(n-2)}{2}-rs,&{} \text{ if } \kappa =1\text{, }\\ \frac{(n-\kappa )(n+\kappa -3)}{2}+\frac{(\kappa -1)(\kappa -2)}{2}-\frac{rs}{2}, &{} \text{ if } \kappa \geqslant 2\text{. } \end{array}\right. } \end{aligned}$$

So

$$\begin{aligned} F(\kappa , r,s)\leqslant f(n, \kappa ):={\left\{ \begin{array}{ll} \frac{(n-2)(n-3)}{2},&{} \text{ if } \kappa =1,\\ \frac{(n-1)(n-3)+\kappa }{2},&{} \text{ if } \kappa \geqslant 2 \end{array}\right. } \end{aligned}$$

(2)

with equality if and only if $r=1$ and $s=n-\kappa -1$. By combining (1) and (2), and noting that $f(n, \kappa )=R(K_{\kappa }\vee (K_1\cup K_{n-\kappa -1}))$, we have

$$\begin{aligned} R(G)=f(n, \kappa ). \end{aligned}$$

Note that G is a spanning subgraph of $K_\kappa \vee (K_r\cup K_s)$. By the above proof, we have $r=1$ and $s=n-\kappa -1$, i.e.,

$$\begin{aligned} G\subseteq K_{\kappa }\vee (K_1\cup K_{n-\kappa -1}). \end{aligned}$$

It is possible that $G\cong K_{\kappa }\vee (K_1\cup K_{n-\kappa -1})$. Suppose in the following that $G \not \cong K_{\kappa }\vee (K_1\cup K_{n-\kappa -1})$. For convenience, let $H=K_{\kappa }\vee (K_1\cup K_s)$ with $s=n-\kappa -1$. Then $G \not \cong H$, so $G\subseteq H-e$ for some edge e of H. Let $V_1, V_2$ and $V_3$ be the vertex sets of the subgraphs $K_{\kappa }$, $K_1$ and $K_s$ appearing in H, respectively. There are four cases.

Case 1 e joins two vertices in $V_1$.

In this case, $\kappa \geqslant 2$. We will prove that $\kappa = 2$. If $\kappa \geqslant 3$, then we choose a vertex u in $V_1$ that is not incident to e in H, so

$$\begin{aligned} C(H-e-u)&= \frac{(\kappa -1)(\kappa -2)}{2}-\frac{1}{2}+\frac{s(s-1)}{2}\\&\quad +(\kappa -1)(1+s)+\frac{s}{2}\\&= F(\kappa , 1,s)-\frac{1}{2}\\&= f(n, \kappa )-\frac{1}{2}. \end{aligned}$$

By Lemma 1, $R(G)\leqslant R(H-e)\leqslant C(H-e-u)<f(n, \kappa )$, which is a contradiction. So $\kappa =2$.

Next, we show that $R(H-e)=f(n,2)$. For any vertex $u\in V_1$,

$$\begin{aligned} C(H-e-u)=C(K_{1}\vee (K_1\cup K_{s}))=\frac{s(s-1)}{2}+1+s+\frac{s}{2}. \end{aligned}$$

For $v \in V_2$ and $w\in V_3$,

$$\begin{aligned} C(H-e-v)=\frac{1}{2}+\frac{s(s-1)}{2}+2s \end{aligned}$$

and

$$\begin{aligned} C(H-e-w)=\frac{1}{2}+\frac{(s-1)(s-2)}{2}+2s+\frac{s-1}{2}. \end{aligned}$$

By direct calculation, we have

$$\begin{aligned} C(H-e-v)-C(H-e-w)=\frac{s-1}{2}\geqslant 0, \end{aligned}$$

$$\begin{aligned} C(H-e-w)-C(H-e-u)=0, \end{aligned}$$

and so $C(H-e-u)= C(H-e-w)\leqslant C(H-e-v)$. Thus,

$$\begin{aligned} R(H-e)&=C(H-e-u)\\&=\frac{s(s-1)}{2}+1+s+\frac{s}{2}\\&=F(2,1,s)\\&=f(n,2). \end{aligned}$$

Now we show that $G\cong H-e$. Suppose that this is not true. Then $G\subseteq H-e-e^*$ for some edge $e^*$ of $H-e$. For convenience, let $H^*=H-e-e^*$. If $s=1$, then $H^*$ is a path on four vertices and so $\kappa \leqslant 1$, a contradiction. So $s\geqslant 2$. If $e^*$ joins a vertex, say u, in $V_1$ and the vertex in $V_2$ of $H-e$, it is easy to see that $V_1\setminus \{u\}$ is a vertex cut of $H^*$, so $\kappa \leqslant |V_1\setminus \{u\}|=1$, a contradiction. So $e^*$ joins a vertex in $V_1$ and a vertex in $V_3$ of $H-e$, or $e^*$ joins two vertices in $V_3$ of $H-e$. In the former case, for a vertex $u\in V_1$ that is incident to e but not incident to $e^*$, we have

$$\begin{aligned} C(H^*-u)=\frac{s(s-1)}{2}+1+s-\frac{1}{2}+\frac{s}{2}-\frac{1}{4} =F(2,1,s)-\frac{3}{4} < f(n,2), \end{aligned}$$

implying that $R(G)\leqslant R(H^*)\leqslant C(H^*-u)< f(n,2)$, which is a contradiction. In the latter case, for $u\in V_1$, we have

$$\begin{aligned} C(H^*-u)=\frac{s(s-1)}{2}-\frac{1}{2}+1+s+\frac{s}{2}=F(2,1,s)-\frac{1}{2}<f(n,2), \end{aligned}$$

implying that $R(G)\leqslant R(H^*)\leqslant C(H^*-u)< f(n,2)$, which is also a contradiction. Therefore, we conclude that $G\cong H-e\cong 2K_1\vee (K_1\cup K_{n-3})$.

Case 2 e joins two vertices in $V_3$.

In this case, $s\geqslant 2$. Let $u\in V_1$. If $\kappa = 1$, then

$$\begin{aligned} C(H-e-u)&= {\left\{ \begin{array}{ll} 0, &{} \text{ if } s=2\\ \frac{s(s-1)}{2}-\frac{1}{2}=F(1, 1,s)-\frac{1}{2}, &{} \text{ if } s>2 \end{array}\right. }\\&< f(n,1), \end{aligned}$$

so $R(G)\leqslant R(H-e)\leqslant C(H-e-u)<f(n,1)$, which is a contradiction. If $\kappa \geqslant 2$, then

$$\begin{aligned} C(H-e-u)&=\frac{(\kappa -1)(\kappa -2)}{2}+\frac{s(s-1)}{2}-\frac{1}{2}\\&\quad +(\kappa -1)(1+s)+\frac{s}{2}\\&= F(\kappa , 1,s)-\frac{1}{2}\\&< f(n,\kappa ), \end{aligned}$$

so $R(G)\leqslant R(H-e)\leqslant C(H-e-u)<f(n,\kappa )$, which is also a contradiction. Therefore, Case 2 cannot occur.

Case 3 e joins a vertex in $V_1$ and a vertex in $V_2$.

If $\kappa =1$, then $H-e$ is disconnected and so G is disconnected, which is a contradiction. So we may assume that $\kappa \geqslant 2$. Let $u\in V_1$ that is not incident to e. Then

$$\begin{aligned}&\quad C(H-e-u)\\&={\left\{ \begin{array}{ll} \frac{s(s-1)}{2} +s, &{} \text{ if } \kappa = 2\\ \frac{(\kappa -1)(\kappa -2)}{2}+\frac{s(s-1)}{2}+(\kappa -1)(1+s)-\frac{1}{2}+\frac{s}{2}, &{} \text{ if } \kappa \geqslant 3 \end{array}\right. }\\&\leqslant \frac{(\kappa -1)(\kappa -2)}{2}+\frac{s(s-1)}{2}+(\kappa -1)(1+s)-\frac{1}{2}+\frac{s}{2}\\&= F(\kappa , 1, s)-\frac{1}{2} \\&< f(n, \kappa ). \end{aligned}$$

Thus, $R(G)\leqslant R(H-e)\leqslant C(H-e-u)<f(n,\kappa )$, which is also a contradiction. So Case 3 cannot occur.

Case 4 e joins a vertex in $V_1$ and a vertex in $V_3$.

If $\kappa \geqslant 2$, then, for $u\in V_1$ that is not incident to e, we have

$$\begin{aligned}&\quad C(H-e-u)\\&= {\left\{ \begin{array}{ll} 1, &{} \text{ if } \kappa = 2, s=1\\ \frac{s(s-1)}{2}+(1+s)-\frac{1}{2}+\frac{s}{2}-\frac{1}{4}, &{} \text{ if } \kappa = 2, s\geqslant 2\\ \frac{(\kappa -1)(\kappa -2)}{2}+\frac{s(s-1)}{2}+(\kappa -1)(1+s)-\frac{1}{2}+\frac{s}{2}, &{} \text{ if } \kappa \geqslant 3 \end{array}\right. }\\&< f(n, \kappa ) \end{aligned}$$

implying that $R(G)\leqslant R(H-e)\leqslant C(H-e-u)<f(n, \kappa )$, which is a contradiction. So $\kappa =1$. Then, $s\geqslant 2$. We show that $R(H-e)=f(n, 1)$. For $u\in V_1$ and $v\in V_2$, we have

$$\begin{aligned} C(H-e-u)=C(K_1\cup K_s)=\frac{s(s-1)}{2} \end{aligned}$$

and

$$\begin{aligned} C(H-e-v)=\frac{s(s-1)}{2}+s-\frac{1}{2}. \end{aligned}$$

For $w_1, w_2 \in V_3$, where $w_1$ is incident to e and $w_2$ is not incident to e, we have

$$\begin{aligned} C(H-e-w_1)&= C(K_1\vee (K_1\cup K_{s-1}))\\&=\frac{(s-1)(s-2)}{2}+ s+\frac{s-1}{2} \end{aligned}$$

and

$$\begin{aligned} C(H-e-w_2)= {\left\{ \begin{array}{ll} C(K_2)=1, &{} \text{ if } s=2\text{, }\\ \frac{(s-1)(s-2)}{2}+s-\frac{1}{2}+\frac{s-1}{2}-\frac{1}{4}, &{} \text{ if } s\geqslant 3\text{. } \end{array}\right. } \end{aligned}$$

By direct calculation, we have

$$\begin{aligned} C(H-e-v)-C(H-e-u)=\frac{2s-1}{2}> 0, \end{aligned}$$

$$\begin{aligned} C(H-e-w_1)-C(H-e-u)=\frac{s+1}{2}>0 \end{aligned}$$

and

$$\begin{aligned} C(H-e-w_2)-C(H-e-u)={\left\{ \begin{array}{ll} 0 , &{} \text{ if } s=2\text{, }\\ \frac{2s-1}{4} >0, &{} \text{ if } s\geqslant 3\text{. } \end{array}\right. } \end{aligned}$$

So $C(H-e-u)\leqslant \min \{C(H-e-v),C(H-e-w_1),C(H-e-w_2)\}$. Thus

$$\begin{aligned} R(H-e)=C(H-e-u)=F(1,1,s)= f(n,1)=\frac{s(s-1)}{2}. \end{aligned}$$

Note that $H-e \cong H_{n,1}$. If $n=4$, then $G\cong H-e\cong H_{4,1}$. Suppose that $n\geqslant 5$. We may assume that $G=H-E$, where E is a subset of edges of H with $e\in E$.

Note that no edge of E joins the vertex in $V_1$ and the vertex in $V_2$, as otherwise, G is disconnected, which is impossible. If there exists an edge of E joins two vertices in $V_3$ of $H-e$, then by letting $u\in V_1$, we have

$$\begin{aligned} C(G-u)\leqslant \frac{s(s-1)}{2}-\frac{1}{2}=f(n,1)-\frac{1}{2}, \end{aligned}$$

so $R(G)\leqslant C(G-u)<f(n,1)$, which is a contradiction. Thus any edge in E joins the vertex in $V_1$ and a vertex in $V_3$ of H. That is, $G\cong H_{n, |E|}$. By Lemma 5, we have $1\leqslant |E|\leqslant \min \{n-4, \lfloor \frac{2(n-1)}{3}\rfloor \}$.

We complete the proof by combining the above cases.

4 Residual Closeness and Edge Connectivity

In this section, we determine all connected graphs with fixed number of vertices and edge connectivity having maximum residual closeness. Note that $K_n$ is the unique connected graph on n vertices with edge connectivity $n-1$ by Lemma 2.

Theorem 2

Let G be a connected graph on n vertices with edge connectivity $\lambda$, where $1\leqslant \lambda \leqslant n-2$. Then,

$$\begin{aligned} R(G)\leqslant {\left\{ \begin{array}{ll} \frac{(n-2)(n-3)}{2}, &{} \text{ if } \lambda =1,\\ \frac{(n-1)(n-3)+\lambda }{2} ,&{} \text{ if } \lambda \geqslant 2 \end{array}\right. } \end{aligned}$$

with equality if and only if G is isomorphic to one of the following graphs:

• (i) $K_1\vee (K_1\cup K_{n-2})$, or $H_{4,1}$, or $H_{n,\ell }$ with $n\geqslant 5$ and $\ell =1, \cdots , \min \{n-4, \lfloor \frac{2(n-1)}{3}\rfloor \}$, if $\lambda =1$;

• (ii) $K_2\vee (K_1\cup K_{n-3})$ or $2K_1\vee (K_1\cup K_{n-3})$, if $\lambda =2$;

• (iii) $K_{\lambda }\vee (K_1\cup K_{n-\lambda -1})$, if $\lambda \geqslant 3$.

Proof

Let G be a connected graph on n vertices with edge connectivity $\lambda$ that maximizes the vertex residual closeness.

Let $\kappa$ be the connectivity of G. Then, $\kappa \leqslant \lambda$ by Lemma 2. If $\lambda =\kappa$, then we have by Theorem 1 that

$$\begin{aligned} R(G)=f(n, \lambda ):= {\left\{ \begin{array}{ll} \frac{(n-2)(n-3)}{2}, &{} \text{ if } \lambda =1,\\ \frac{(n-1)(n-3)+\lambda }{2} ,&{} \text{ if } \lambda \geqslant 2, \end{array}\right. } \end{aligned}$$

and G is isomorphic to one of $K_{\lambda }\vee (K_1\cup K_{n-\lambda -1})$, or $2K_1\vee (K_1\cup K_{n-3})$, or $H_{4,1}$, or $H_{n,\ell }$ with $n\geqslant 5$ and $\ell =1, \cdots , \min \{n-4, \lfloor \frac{2(n-1)}{3}\rfloor \}$. If $\lambda >\kappa$, then $R(G)\leqslant f(n, \kappa )<f(n, \lambda )$, which is a contradiction.

Similarly, we have

Corollary 1

Let G be a connected graph on n vertices with minimum degree $\delta$, where $1\leqslant \delta \leqslant n-2$. Then,

$$\begin{aligned} R(G)\leqslant {\left\{ \begin{array}{ll} \frac{(n-2)(n-3)}{2}, &{} \text{ if } \delta =1,\\ \frac{(n-1)(n-3)+\delta }{2}, &{} \text{ if } \delta \geqslant 2 \end{array}\right. } \end{aligned}$$

with equality if and only if G is isomorphic to one of the following graphs:

• (i) $K_1\vee (K_1\cup K_{n-2})$, or $H_{4,1}$, or $H_{n,\ell }$ with $n\geqslant 5$ and $\ell =1, \cdots , \min \{n-4, \lfloor \frac{2(n-1)}{3}\rfloor \}$, if $\delta =1$;

• (ii) $K_2\vee (K_1\cup K_{n-3})$ or $2K_1\vee (K_1\cup K_{n-3})$, if $\delta =2$;

• (iii) $K_{\delta }\vee (K_1\cup K_{n-\delta -1})$, if $\delta \geqslant 3$.

5 Residual Closeness and Bipartiteness

In this section, we determine all connected graphs with fixed number of vertices and bipartiteness having maximum residual closeness.

Lemma 6

Suppose that $G=K_k\vee K_{r,t}$ with $k,r, t\geqslant 1$ and $k+r+t=n$. Then

$$\begin{aligned} R(G)= \frac{(k-1)(k-2)}{2}+\frac{(n-k)(n+3k-5)}{4}+\frac{rt}{2}. \end{aligned}$$

Proof

Let $U=V(K_k)$. Then, $G-U=K_{r,t}$. Let $\{X,Y\}$ be the bipartition of $G-U$ with $|X|=r$ and $|Y|=t$. Let $u\in U$, $x\in X$ and $y\in Y$. Then,

$$\begin{aligned} C(G-u)={k-1\atopwithdelims ()2}+(k-1)(r+t)+rt + \frac{1}{2}\left( {r\atopwithdelims ()2}+{t\atopwithdelims ()2} \right) , \end{aligned}$$

$$\begin{aligned} C(G-x)={k\atopwithdelims ()2}+k(r-1+t)+(r-1)t + \frac{1}{2}\left( {r-1\atopwithdelims ()2}+{t\atopwithdelims ()2} \right) , \end{aligned}$$

and

$$\begin{aligned} C(G-y)={k\atopwithdelims ()2}+k(r+t-1)+r(t-1) + \frac{1}{2}\left( {r\atopwithdelims ()2}+{t-1\atopwithdelims ()2} \right) . \end{aligned}$$

Assume that $r\geqslant t$. By straightforward computation, we see that

$$\begin{aligned} C(G-x)-C(G-y)=\frac{r-t}{2}\geqslant 0 \end{aligned}$$

and

$$\begin{aligned} C(G-y)-C(G-u)=\frac{t-1}{2}\geqslant 0. \end{aligned}$$

So we have

$$\begin{aligned} R(G)&=C(G-u)\\&=\frac{(k-1)(k-2)}{2}+(k-1)(r+t)+rt+\frac{r(r-1)+t(t-1)}{4}\\&=\frac{(k-1)(k-2)}{2}+\frac{(n-k)(n+3k-5)}{4}+\frac{rt}{2}, \end{aligned}$$

as desired.

For integers $t\geqslant r \geqslant 2$, we call any edge of $K_1\vee K_{r,t}$ with one end vertex of degree $r+t$ a non-bipartite edge.

Lemma 7

For integers $t\geqslant r \geqslant 2$ and q with $1\leqslant q \leqslant r+t-1$, let E be a set of q non-bipartite edges of $K_1\vee K_{r,t}$. Let $G=K_1\vee K_{r,t}-E$. If the bipartiteness of G is 1, then $R(G)=\frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}$ if and only if $1 \leqslant q \leqslant r-1$.

Proof

Let u be the vertex of degree $r+t$ in $K_1\vee K_{r,t}$, and $\{X,Y\}$ the bipartition of $K_1\vee K_{r,t}-u$ with $|X|=r$ and $|Y|=t$.

Since G is a graph with bipartiteness one, $q\leqslant r+t-2$ and ux and uy are edges of G for some $x\in X$ and some $y\in Y$. As $q\geqslant 1$, $uw\in E$ for some $w\in X\cup Y$. Then,

$$\begin{aligned} C(G-u)=rt+ \frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) = \frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}, \end{aligned}$$

$$\begin{aligned} C(G-x)&=(r-1+t)-\frac{q}{2}+(r-1)t+ \frac{1}{2}\left( \left( {\begin{array}{c}r-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) \\&= \frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}+\frac{r-q-1}{2}, \end{aligned}$$

$$\begin{aligned} C(G-y)&=(r+t-1)-\frac{q}{2}+r(t-1)+ \frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) \right) \\&=\frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}+\frac{t-q-1}{2}, \end{aligned}$$

and

$$\begin{aligned} C(G-w) ={\left\{ \begin{array}{ll} C(G-x)+\frac{1}{2} ,&{} \text{ if } w\in X, \\ C(G-y)+\frac{1}{2}, &{} \text{ if } w\in Y. \end{array}\right. } \end{aligned}$$

Suppose first $R(G)=\frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}$. If $q\geqslant r$, then $R(G)\leqslant C(G-x)<\frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}$, which is a contradiction. It follows that $1\leqslant q \leqslant r-1$.

Conversely, suppose that $1 \leqslant q \leqslant r-1$, then

$$\begin{aligned} C(G-u)\leqslant \min \{ C(G-x), C(G-y)\} < C(G-w), \end{aligned}$$

so $R(G)= C(G-u)=\frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}$.

Theorem 3

Let G be a connected graph on $n\geqslant 4$ vertices with bipartiteness k, where $0\leqslant k\leqslant n-2$. Then,

$$\begin{aligned} R(G)\leqslant {\left\{ \begin{array}{ll} \frac{(n-1)(n-2)}{4}+\frac{1}{2}\left( \left\lfloor \frac{n}{2}\right\rfloor -1\right) \left\lceil \frac{n}{2}\right\rceil , &{} \text{ if } k=0,\\ \frac{(k-1)(k-2)}{2}+\frac{(n-k)(n+3k-5)}{4}+\frac{1}{2} \lceil \frac{n-k}{2}\rceil \lfloor \frac{n-k}{2} \rfloor , &{} \text{ if } k\geqslant 1 \end{array}\right. } \end{aligned}$$

with equality if and only if G is isomorphic to one of the following graphs:

• (i) $K_{\lfloor n/2\rfloor , \lceil n/2\rceil }$, if $k=0$;

• (ii) $K_1\vee K_{\lfloor (n-1)/2\rfloor , \lceil (n-1)/2\rceil }$, or $K_1\vee K_{\lfloor (n-1)/2\rfloor , \lceil (n-1)/2\rceil }-E$ for a set E of non-bipartite edges with $1\leqslant |E| \leqslant \lfloor \frac{n-1}{2} \rfloor -1$, if $k=1$;

• (iii) $K_2\vee K_{\lfloor (n-2)/2\rfloor , \lceil (n-2)/2\rceil }$, or $2K_1\vee K_{\lfloor (n-2)/2 \rfloor , \lceil (n-2)/2\rceil }$ with $n\geqslant 6$, if $k=2$;

• (iv) $K_{k}\vee K_{\lfloor (n-k)/2\rfloor , \lceil (n-k)/2\rceil }$, if $k\geqslant 3$.

Proof

The case when $k=0$ follows from Lemma 3. Suppose that $k\geqslant 1$. Let G be a connected graph on n vertices with bipartiteness k that maximizes the residual closeness.

Let $U\subset V(G)$ with $|V(U)|=k$ such that $G-U$ is a bipartite graph. Let $\{X,Y\}$ be the bipartition of $G-U$. Let $r=|X|$ and $t=|Y|$. Assume that $r\leqslant t$. So $G\subseteq K_k\vee K_{r,t}$. By Lemmas 1 and 6, we have

$$\begin{aligned} R(G)=R(K_k\vee K_{r,t}) = \frac{(k-1)(k-2)}{2}+\frac{(n-k)(n+3k-5)}{4}+\frac{rt}{2}. \end{aligned}$$

(3)

The above upper bound (3) for R(G) is maximized if and only if $r=\lfloor \frac{n-k}{2} \rfloor$ and $t=\lceil \frac{n-k}{2}\rceil$. Note that the maximum value is really achieved by $K_{k}\vee K_{\lfloor (n-k)/2\rfloor , \lceil (n-k)/2\rceil }$. Thus, we have

$$\begin{aligned} R(G)=g(n,k):= & {} \frac{(k-1)(k-2)}{2}+\frac{(n-k)(n+3k-5)}{4}\\&+\frac{1}{2} \left\lceil \frac{n-k}{2}\right\rceil \left\lfloor \frac{n-k}{2} \right\rfloor . \end{aligned}$$

For convenience, let $G'=K_k\vee K_{r,t}$. Note that G is a spanning subgraph of $G'$. By the above proof, we have

$$\begin{aligned} r=\left\lfloor \frac{n-k}{2} \right\rfloor \text{ and } t=\left\lceil \frac{n-k}{2}\right\rceil . \end{aligned}$$

That is,

$$\begin{aligned} G' =K_{k}\vee K_{\lfloor (n-k)/2\rfloor , \lceil (n-k)/2\rceil }. \end{aligned}$$

It is possible that $G\cong G'\cong K_{k}\vee K_{\lfloor (n-k)/2\rfloor , \lceil (n-k)/2\rceil }$. Suppose in the following that $G \not \cong G'$. Then $G\subseteq G'-e$ for some edge e of $G'$. There are three cases.

Case 1 e joins two vertices in U.

In this case, $k\geqslant 2$. We claim that $k= 2$. Otherwise, $k\geqslant 3$. We choose a vertex u in U, which is not incident to e, so we have

$$\begin{aligned} C(G'-e-u)&=\frac{(k-1)(k-2)}{2}-\frac{1}{2}+(k-1)(r+t)+rt+ \frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) \\&=\frac{(k-1)(k-2)}{2}+\frac{(n-k)(n+3k-5)}{4}+\frac{rt}{2}-\frac{1}{2}\\&=g(n,k)-\frac{1}{2}\\&<g(n,k). \end{aligned}$$

By Lemma 1,

$$\begin{aligned} R(G) \leqslant R(G'-e)\leqslant C(G'-e-u) < g(n,k), \end{aligned}$$

which is a contradiction. So $k=2$, as claimed.

Suppose that $r=1$. That is, $n=4,5$. Then, $t=1,2$ and the deletion of the unique vertex in X from $G'-e$ results in a bipartite graph $K_{2,t}$, and so the bipartiteness of $G'-e$ is 1. As G is a spanning subgraph of $G'-e$, the bipartiteness of G is no more than that of $G'-e$, so $k\leqslant 1$, which contradicts the fact that $k=2$. It follows that $r \geqslant 2$. That is, $n\geqslant 6$.

Next, we show that $R(G'-e)=g(n,2)$. For any vertex $u\in U$, $x \in X$ and $y \in Y$, we have

$$\begin{aligned} C(G'-e-u)=C(K_{1}\vee K_{r,t})=r+t+rt+\frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) , \end{aligned}$$

$$\begin{aligned} C(G'-e-x)=\frac{1}{2}+2(r-1+t)+(r-1)t+\frac{1}{2}\left( \left( {\begin{array}{c}r-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) \end{aligned}$$

and

$$\begin{aligned} C(G'-e-y)=\frac{1}{2}+2(r+t-1)+r(t-1)+\frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) \right) . \end{aligned}$$

By direct calculation, we see that

$$\begin{aligned} C(G'-e-x)-C(G'-e-u)=\frac{r-2}{2}\geqslant 0 \end{aligned}$$

and

$$\begin{aligned} C(G'-e-y)-C(G'-e-u)=\frac{t-2}{2}\geqslant 0. \end{aligned}$$

Thus,

$$\begin{aligned} R(G'-e)&=C(G'-e-u)\\&= r+t+rt+\frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) \\&= \frac{(r+t)^2+3(r+t)}{4}+\frac{rt}{2}\\&= g(n,2). \end{aligned}$$

Now, we show that $G\cong G'-e$. Suppose that this is not true. Then $G\subseteq G'-e-e^*$ for some edge $e^*$ of $G'-e$. For convenience, let $G^*=G'-e-e^*$. Denote by u the vertex in U that is not incident to $e^*$ in $G'-e$ if $e^*$ joins a vertex in U and a vertex in X or Y, and either vertex in U otherwise. In both cases, we have

$$\begin{aligned} C(G^*-u)=r+t+rt-\frac{1}{2}+\frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) = g(n,2)-\frac{1}{2}, \end{aligned}$$

Thus $R(G)\leqslant R(G^*)\leqslant C(G^*-u) <g(n,2)$, a contradiction. So we conclude that $G\cong G'-e\cong 2K_1\vee K_{\lfloor (n-2)/2 \rfloor , \lceil (n-2)/2\rceil }$.

Case 2 e joins a vertex in X and a vertex in Y.

Let $u \in U$. If $k\geqslant 2$, then

$$\begin{aligned} C(G'-e-u)&=\frac{(k-1)(k-2)}{2}+(k-1)(r+t)+rt -\frac{1}{2}\\&\quad +\frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) \\&=g(n,k)-\frac{1}{2}\\&<g(n,k), \end{aligned}$$

so $R(G)\leqslant R(G'-e)\leqslant C(G'-e-u)<g(n,k)$, which is a contradiction. It follows that $k=1$. If $n=4$, then $G'=K_1\vee K_{1,2}$, so $C(G'-e-u)=1<g(4,1)$. If $n\geqslant 5$, then $r\geqslant 2$, $C(G'-e-u)=rt -\frac{3}{4}+\frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right)$, and so

$$\begin{aligned} C(G'-e-u)&=\frac{(n-1)(n-2)}{4}+\frac{1}{2}rt-\frac{3}{4}\\&<g(n,1). \end{aligned}$$

In either case, we have $R(G)\leqslant R(G'-e)\leqslant C(G'-e-u)<g(n,1)$, which is a contradiction. So Case 2 cannot occur.

Case 3 e joins a vertex in U and a vertex in $X\cup Y$.

Suppose that $k\geqslant 2$. We choose a vertex u in U that is not incident to e, and we have

$$\begin{aligned} C(G'-e-u)&=\frac{(k-1)(k-2)}{2}+(k-1)(r+t)-\frac{1}{2}+rt\\&\quad + \frac{1}{2}\left( \left( {\begin{array}{c}r\\ 2\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) \right) \\&=\frac{(k-1)(k-2)}{2}+\frac{(n-k)(n+3k-5)}{4}+\frac{rt}{2}-\frac{1}{2}\\&<g(n,k). \end{aligned}$$

By Lemma 1,

$$\begin{aligned} R(G) \leqslant R(G'-e)\leqslant C(G'-e-u) < g(n,k), \end{aligned}$$

which is a contradiction. It follows that $k=1$ with $g(n,1)=\frac{(r+t)(r+t-1)}{4}+\frac{rt}{2}$.

As G is a spanning subgraph of $G'-e$ and the bipartiteness of G is 1, the bipartiteness of $G'-e$ is at least 1. If $n=4$, then $r=1$, e must join the unique vertex in U and a vertex in Y, and $C(G'-e-x)=C(K_2\cup K_1)=1<\frac{5}{2}=g(4,1)$ for $x\in X$, a contradiction. Thus, $n\geqslant 5$.

We may assume that $G=G'-E$, where E is a subset of edges of $G'$ with $e\in E$. By the above arguments, any edge of E joins the unique vertex in U and a vertex in $X\cup Y$. By Lemma 7, we have $|E|\leqslant \lfloor \frac{n-1}{2} \rfloor -1$. Thus, $G\cong G'-E$ with $1\leqslant |E|\leqslant \lfloor \frac{n-1}{2} \rfloor -1$.

6 Concluding Remarks

A central concept that is used to assess stability and robustness of the performance of a network under failures is that of vulnerability, see, e.g., [21, 22]. Residual closeness is a new graph vulnerability measure used in network vulnerability analysis [5]. One way to understand which graph properties a graph invariant gauges is to investigate the extremal graphs. In this paper, we studied the relationship between residual closeness and some graph parameters including connectivity, edge connectivity and bipartiteness. Those connected graphs with fixed number of vertices and one of these graph parameters that achieve the maximum residual closeness were completed determined. The extremal graphs can provide a snapshot of the residual closeness and so can yield information about the graph. The results may be extended to the generalized version of the residual closeness in [8] defined as $R_{\alpha }(G)=\min \{C_{\alpha }(G-u): u\in V(G)\}$ with $C_{\alpha }(G)=\sum _{u\in V(G)}\sum _{v\in V(G)\setminus \{u\}}\alpha ^{d_G(u,v)}$, where $\alpha \in (0,1)$. In following steps, we will investigate the relationship between residual closeness and other graph parameters, like number of cut vertices, number of cut edges, matching number, domination number, toughness, scattering number and binding number.