On the residual closeness of graphs with cut vertices

Abstract

In designing and understanding of computer networks, how to improve network robustness or protect a network from vulnerability remains an overarching concern. The residual closeness is a measure of network vulnerability and robustness even when the removal of vertices does not disconnect the underlying graph. We determine all the graphs that minimize and maximize the residual closeness respectively over all n-vertex connected graphs with r cut vertices, where $1\le r\le n-3$.

1 Introduction

A network is usually represented by an undirected simple graph where vertices represent processors and edges represent links between processors. In designing and understanding of computer networks, a central issue is the assessment of their vulnerability and robustness (Boccaletti et al. 2007; Holme et al. 2002). 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. There are a variety of measures of network vulnerability such as connectivity (Frank and Frisch 1970), toughness (Chvátal 1973) and scattering number (Jung 1978), to mention just a few. A newly proposed measure of network vulnerability is the residual closeness introduced by Dangalchev (2006). It aims to measure the vulnerability even when the removal of vertices does not disconnect the graph and can reflect the vulnerability of graphs better than or independent of the other parameters existing in literature (Dangalchev 2006). The computation of the residual closeness of different classes of graphs and even graph operations received much attention, see Aytac and Odabas (2011), Aytac and Berberler (2017), Aytac and Odabas Berberler (2018), Dangalchev (2018), Odabas and Aytac (2013), Turaci and Ökten (2015). It is of also interest to investigate the extremal problem to minimize and/or maximize the residual closeness over different classes of graphs. For example, the classes of connected graphs with fixed connectivity, edge connectivity, bipartiteness, matching number and chromatic number respectively have been considered (Cheng and Zhou 2022; Wang and Zhou 2022; Zhou et al. 2021).

Let G be a graph with vertex set V(G) and edge set E(G). For a graph G with $v\in V(G)$, let $N_G(v)$ be the set of all neighbors of v in G. The degree of $v \in V(G)$, denoted by $\delta _G(v)$, is the cardinality of $N_G(v)$. 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 a vertex u of 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)}$ in Dangalchev (2006) and after 2 years used in Jackson (2008). The closeness of 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}$$

Denote by $G-v$ the graph formed from a nontrivial G by deleting a vertex $v \in V(G)$ (and its incident edges). The (vertex) residual closeness of a nontrivial graph G is defined as (Dangalchev 2006)

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

The residual closeness is a graph based network parameter that measure the network vulnerability or network robustness. Generally, we think that the network is robust if the residual closeness is large, and is vulnerable otherwise.

A vertex v of a connected graph G is a cut vertex if $G-v$ is disconnected. Note that an n-vertex connected graph with $n\ge 2$ possesses at most $n-2$ cut vertices, and if it has $n-2$ cut vertices, then it is the n-vertex path. In this paper, the behavior of networks with cut vertices to the failure of individual vertices is analyzed via residual closeness, and more precisely, we identify the graphs that minimize and maximize the residual closeness respectively over all n-vertex connected graphs with r cut vertices, where $1\le r\le n-3$.

2 Main results

A path $v_0\dots v_s$ in a graph G is a pending path of length s at $v_0$ if $\delta _G(v_0)\ge 3$, $\delta _G(v_s)=1$, and $\delta _G(v_i)=2$ for $i=1,\dots ,s-1$ if $s \ge 2$. For a positive integer $\ell \ge 3$, an $\ell$-starlike tree is a tree with exactly one vertex of degree at least three and the degree of this vertex is $\ell$. This vertex is called the center.

Denote by $S_{n,\ell }$ the n-vertex $\ell$-starlike tree consisting of $\ell$ pending paths at u of lengths $a_1,\dots ,a_{\ell }$ respectively, where $a_1+\dots +a_{\ell }=n-1$, $a_1\ge \dots \ge a_{\ell }$ and $a_1-a_{\ell }=0,1$. Evidently, $S_{n,\ell }$ consists of p pending paths of length $\lfloor \frac{n-1}{\ell }\rfloor +1$ and $\ell -p$ pending path of length $\lfloor \frac{n-1}{\ell }\rfloor$ at a common vertex, where $p=n-1-\ell \lfloor \frac{n-1}{\ell }\rfloor$.

Theorem 2.1

Let G be an n-vertex connected graph with r cut vertices, where $1\le r\le n-3$. Then

$$\begin{aligned} R(G)\ge 4r-2n-2+2^{1-\lfloor \frac{n-1}{n-r}\rfloor }(2(n-r)-p) \end{aligned}$$

with equality if and only if $G\cong S_{n,n-r}$, where $p=n-1-(n-r)\lfloor \frac{n-1}{n-r}\rfloor$.

Let s be an integer with $s\ge 3$. For integers $a_1, \dots , a_s\ge 0$, let $S(a_1,\dots , a_s)$ be the graph containing a subgraph $K_s$ with vertex set $\{v_1,\dots ,v_s\}$ such that the deletion of all edges of $K_s$ results in s vertex disjoint paths $P_{a_1+1},\dots , P_{a_s+1}$ with $v_i$ being an end vertex of the path $P_{a_i+1}$ for $i=1,\dots , s$. Evidently, $|V(S(a_1,\dots , a_s))|=\sum _{i=1}^sa_i+s$. Denote by $G_{n,n-s}$ the graph $S(a_1,\dots ,a_s)$ with $\sum _{i=1}^sa_i=n-s$ and $|a_i-a_j|=0,1$ for any $1\le i<j\le s$.

Theorem 2.2

Let G be an n-vertex connected graph with $n-3$ cut vertices, where $n\ge 4$. Then

$$\begin{aligned} R(G)\le {\left\{ \begin{array}{ll} 2n-10+2^{2-\lceil \frac{n-3}{3}\rceil }+2^{3-n+\lceil \frac{n-3}{3}\rceil } &{} \hbox {if } n=5,6\\ 2n-9+2^{5-n} &{} \hbox {if }n=4 {\hbox { or }} n\ge 7 \end{array}\right. } \end{aligned}$$

with equality if and only if $G\cong S(a_1,a_2,a_3)$ with

$$\begin{aligned} (a_1,a_2, a_3)={\left\{ \begin{array}{ll} (1,1,0) &{} \hbox {if } n=5,\\ (1, 1,1) &{} \hbox {if } n=6,\\ (n-3, 0,0),(2,2,0), (2,1,1) &{} \hbox {if } n=7,\\ (n-3, 0,0), (2,2,1) &{} \hbox {if } n=8, \\ (n-3, 0,0),(2,2,2) &{} \hbox {if } n=9,\\ (n-3, 0,0) &{} \hbox {if } n=4 \,{\hbox {or}}\, n\ge 10. \end{array}\right. } \end{aligned}$$

For positive integers n, r and t with $n=t(n-r)+1$ and $1\le r\le n-4$, denote by v the unique vertex at which the length of pending path is t in $G_{n,r}$. Let $G_{n,r,\ell }$ be the graph obtained from $G_{n,r}$ by deleting $\ell$ edges in the clique of size $n-r$ incident to v, where $1\le \ell \le n-r-2$.

For positive integers n, r and t with $n=t(n-r)+2$, denote by $v_1$ and $v_2$ the only two vertices at which the pending paths are of length t in $G_{n,r}$. Let $G_{n,r}^-=G_{n,r}-v_1v_2$.

Theorem 2.3

Let G be an n-vertex connected graph with r cut vertices, where $1\le r\le n-4$. Let $n=t(n-r)+p$ with $0\le p\le n-r-1$. Then

$$\begin{aligned} R(G)&\le 2(n-r-1)^2-4n+6r+2^{3-t}-4(n-r-1)(n-r-3)2^{-t}\\&\qquad +2(n-r-1)(n-r-2)2^{-2t} \end{aligned}$$

if $p=0$, and

$$\begin{aligned} R(G)&\le 2(n-r-1)^2-4n+6r+2^{2-t}-2(n-r-3)(2n-2r-p-1)2^{-t}\\&\qquad +\left( \frac{(p-1)(p-2)}{2}+2(n-r-p)(n-r-2)\right) 2^{-2t} \end{aligned}$$

otherwise. Moreover, the above bound for R(G) is attained if and only if

$$\begin{aligned} G\cong {\left\{ \begin{array}{ll} G_{n,r}, G_{n,r,\ell } &{} \hbox {if } p=1\,{\hbox {and}}\, \ell \text { satisfies }(2.1),\\ G_{n,r}, G_{n,r}^- &{} \hbox {if } p=2 {\hbox { and}}\,n-r\ge \frac{2^{2t+2}-9}{2^{t+2}-4},\\ G_{n,r} &{} \hbox {otherwise}, \end{array}\right. } \end{aligned}$$

where

$$\begin{aligned} 1\le \ell \le \min \left\{ n-r-3, \frac{(n-r-2)\left( 2^{t+1}-2\right) +2^{t+1}}{2^{2t+1}-3\times 2^{t}+1}\right\} . \end{aligned}$$

(2.1)

3 Preliminaries

For positive integer n, we denote by $K_n$ the n-vertex complete graph and $P_n$ the n-vertex path.

For a graph G with $\emptyset \ne E_1\subseteq E(G)$, $G-E_1$ denotes the graph obtained from G by deleting the edges in $E_1$, and we write $G-e$ for $G-\{e\}$ if $e\in E(G)$.

For a graph G, we denote by $\overline{G}$ the complement of G. If $\emptyset \ne E_1\subseteq E(\overline{G})$, then $G+E_1$ denotes the graph obtained from G by adding the edges of $E_1$, and we write $G+e$ for $G+\{e\}$ if $e\in E(\overline{G})$.

Lemma 3.1

Dangalchev (2006); Zhou et al. (2021) Let G be a graph with $e\in E({\overline{G}})$. Then $C(G)<C(G+e)$.

Lemma 3.2

Wang and Zhou (2022) Let G be a graph with $uv\in E(G)$. Then $R(G-uv)\le R(G)$ for any $uv\in E(G)$. Moreover, if $R(G)=C(G-w)$ and $uv\in E(G-w)$, then $R(G-uv)<R(G)$.

Lemma 3.3

Let G be a graph with a pending path $v_0v_1\dots v_t$ at $v_0$ with $t\ge 1$. Then $C(G-v_i)>C(G-v_0)$ for $i=1,\dots ,t$.

Proof

Let $V_1=V(G)\setminus \{v_0,\dots ,v_t\}$. For $i=1,\dots ,t$, as we pass from $G-v_0$ to $G-v_i$, the distance between any pair of vertices in $V_1$, in $\{v_j:1\le j\le i-1\}$ and in $\{v_j:i+1\le j\le t\}$ remains unchanged. Recall that $\delta _G(v_0)\ge 3$. Then

$$\begin{aligned}&C(G-v_i)-C(G-v_0)\\&\quad = 2\sum _{j=0}^{i-1}\sum _{w\in V_1}2^{-d_G(v_j,w)}-2\sum _{j=1}^{i}\sum _{k=i+1}^t2^{-d_G(v_j,v_k)}\\&\quad =2\sum _{j=0}^{i-1}2^{-d_G(v_j,v_0)}\sum _{w\in V_1}2^{-d_G(v_0,w)}-2\sum _{j=1}^{i}2^{-d_G(v_j,v_i)}\sum _{k=i+1}^t2^{-d_G(v_i,v_k)}\\&\quad =(4-2^{-i+2})\sum _{w\in V_1}2^{-d_G(v_0,w)}-(4-2^{-i+2})(1-2^{-t+i})\\&\quad \ge (4-2^{-i+2})(2\cdot 2^{-1}-1+2^{-t+i})\\&\quad >0 \end{aligned}$$

as desired. $\square$

Lemma 3.4

For integers n and s with $s\ge 3$ and $n-s\ge 1$, let $G=S(a_1,\dots ,a_s)$, where $a_1\ge \dots \ge a_s\ge 0$ and $\sum _{i=1}^s a_i+s=n$. Then $R(G)=C(G-v_1)$.

Proof

For $i=1,\dots ,s$, let $Q_i$ be the pending path at $v_i$ in G.

Assume that $R(G)=C(G-x)$ for some $x\in V(G)$. By Lemma 3.3, $x\in \{v_1,\dots ,v_s\}$.

As $n-s\ge 1$, $a_1\ge 1$. For $i=2,\dots ,s$, if $a_i=0$, then $G-v_1$ is isomorphic to a proper spanning subgraph of $G-v_i$, so $C(G-v_i)>C(G-v_1)$. Therefore $x\in \{v_i:a_i\ge 1\}$. Suppose that $1\le a_i<a_1$. Let $V_0=V(G)\setminus (V(Q_1)\cup V(Q_i))$. As we pass from $G-v_1$ to $G-v_i$, the distance between any pair of vertices in $V_0$, in $V(Q_1)\setminus \{v_1\}$ and in $V(Q_i)\setminus \{v_i\}$ remains unchanged. Then

$$\begin{aligned}&C(G-v_i)-C(G-v_1)\\&\quad =2\sum _{z\in V(Q_1)}\sum _{w\in V_0}2^{-d_G(z,w)}+2\sum _{z\in V(Q_1)\setminus \{v_1\}}2^{-d_G(z,v_1)}\\&\qquad -2\sum _{z\in V(Q_i)}\sum _{w\in V_0}2^{-d_G(z,w)}-2\sum _{z\in V(Q_i)\setminus \{v_i\}}2^{-d_G(z,v_i)}\\&\quad =2\sum _{z\in V(Q_1)}2^{-d_G(z,v_1)}\sum _{w\in V_0}2^{-d_G(v_1,w)}+2-2^{1-a_1}\\&\qquad -2\sum _{z\in V(Q_i)}2^{-d_G(z,v_i)}\sum _{w\in V_0}2^{-d_G(v_i,w)}-(2-2^{1-a_i})\\&\quad =\left( 2^{-a_i}-2^{-a_1} \right) \left( \sum _{w\in V_0}2^{1-d_G(v_1,w)}+2\right) \\&\quad >0, \end{aligned}$$

so $x\ne v_i$. It thus follows that $x\in \{v_i: a_i=a_1\}$. $\square$

4 Proof of Theorem 2.1

To prove Theorem 2.1, we need the following three lemmas.

Lemma 4.1

Zhou et al. (2021) Let T be a tree on $n\ge 3$ vertices. Then

$$\begin{aligned} C(T)\ge 2n-4+2^{2-n} \end{aligned}$$

with equality if and only if $T\cong P_n$.

Lemma 4.2

Zhou et al. (2021) Let F be an n-vertex forest consisting of $\ell$ vertex disjoint paths, where $\ell \ge 2$. Let $r=n-\ell \lfloor \frac{n}{\ell }\rfloor$. Then

$$\begin{aligned} C(F)\ge 2n-4\ell +2^{1-\lfloor \frac{n}{\ell }\rfloor }(2\ell -r) \end{aligned}$$

with equality if and only if these paths have almost equal lengths, that is, the difference between the longest and the shortest ones is 0 or 1.

Lemma 4.3

Zhou et al. (2021) For $3\le \ell \le n-2$, $R(S_{n, \ell })>R(S_{n, \ell +1})$.

Proof of Theorem 2.1

Let G be the graph that minimizes the residual closeness among all n-vertex connected graph with r cut vertices. Assume that $R(G)=C(G-u)$.

Claim A. Any component of $G-u$ contains a vertex that is not a cut vertex of G.

Let H be a component of $G-u$. If H is trivial, then the unique vertex of H is of degree one in G, so it is not a cut vertex of G. Suppose that H is nontrivial. Then it has at least two vertices (say v and w) that are not cut vertices of H. Let Q be a path connecting v and w in H. If u is adjacent to both v and w in G, then v and w lie on a cycle of G containing Q and edges uv and uw, which implies neither v nor w is a cut vertex of G. If u is not adjacent to one of v and w, say v, then v is not a cut vertex of G, as otherwise, it will be a cut vertex of H, which is a contradiction. So in any case H contains a vertex that is not a cut vertex of G. This proves Claim A.

By Claim A, $G-u$ has at most $n-r$ components. Let $G_1,\dots , G_t$ be all the components of $G-u$, where $t\le n-r$. Then $R(G)=\sum _{j=1}^{t}C(G_i)$. Let $a_j=|V(G_j)|$ for $j=1, \dots , t$. Assume that $a_1\ge \dots \ge a_{t}$. By Lemmas 3.1 and 4.1 as well as the choice of G, we have $G_j\cong P_{a_j}$ for $j=1,\dots , t$, and $R(G)=\sum _{i=1}^{t}C(P_{a_i})$.

Claim B. $R(G)=R(S_{n,n-r})$, $t=n-r$ and $a_1-a_{n-r}=0,1$.

By Lemma 4.2,

$$\begin{aligned} R(G)=\sum _{i=1}^{t}C(P_{a_i})\ge C(S_{n,t}-z)\ge R(S_{n,t}), \end{aligned}$$

with equalities only if $a_1-a_{t}=0,1$, where z the unique vertex of $S_{n,t}$ with degree large than two. Now, by Lemma 4.3, $R(G)\ge R(S_{n,n-r})$ with equality only if $t=n-r$. Note that $S_{n,n-r}$ possesses r cut vertices. By the choice of G, $R(G)\le R(S_{n,n-r})$. It follows that $R(G)=R(S_{n,n-r})$, so Claim B follows.

By Claim B, $R(G)= R(S_{n,n-r})$ and $a_1-a_{n-r}=0,1$. Let $p=n-1-(n-r)\lfloor \frac{n-1}{n-r}\rfloor$. Then

$$\begin{aligned} R(S_{n,n-r})&=R(G)=\sum _{j=1}^{n-r} C(P_{a_j})\\&= 2(n-1)-4(n-r)+2^{1-\lfloor \frac{n-1}{n-r}\rfloor }(2(n-r)-p)\\&=4r-2n-2+2^{1-\lfloor \frac{n-1}{n-r}\rfloor }(2(n-r)-p). \end{aligned}$$

By Claim B, $t=n-r$. By Claim A, any component of $G-u$ contains exactly one vertex that is not a cut vertex of G.

If u is adjacent to some vertex of degree two in $G_j$ for some $j=1,\dots ,n-r$, then neither of the two terminal vertices of $P_{a_j}$ is a cut vertex of G, which is a contradiction. So u is not adjacent to any vertex of degree two in $G-u$. If u has at least two neighbors, say $v_1, v_2$, in $G_j$ for some $j=1,\dots ,n-r$, then $v_1$ and $v_2$ lie on a cycle of G, so neither of them is a cut vertex, which is also a contradiction. Thus, u is adjacent to exactly one terminal vertex of the path $P_{a_j}$ for each $j=1,\dots , n-r$. That is, $G\cong S_{n,n-r}$. $\square$

5 Proof of Theorem 2.2

A connected graph with no cut vertices is called a block. A block of a graph is a subgraph that is a block and is maximal with respect to this property.

A clique graph is a graph consisting of blocks so that every block is a clique and every cut vertex is contained in exactly two blocks. If G is a clique graph with k cut vertices, then it possesses $k+1$ blocks.

Proof of Theorem 2.2

Let G be the graph with maximum residual closeness among all n-vertex connected graphs with $n-3$ cut vertices.

Let H be the graph obtained from G by adding all possible edges such that any cut vertex of G is still a cut vertex of H. Then H is a clique graph on n vertices with $n-3$ cut vertices and $n-2$ blocks, where each block contains at least two vertices. By Lemma 3.2, $R(G)=R(H)$.

Let $n_1\ge \dots \ge n_{n-2}$ be the sizes of the blocks of H. As $n_1+\dots +n_{n-2}=n+n-3$ and $n_{n-2}\ge 2$, we have $n_1=3$ and $n_2=\dots =n_{n-2}=2$. So $H\cong S(a_1,a_2, a_3)$ with $a_1\ge a_2\ge a_3$.

If $n=4$, then $H\cong S(1,0,0)$ with $R(H)=C(P_2)=1$. Suppose that $n\ge 5$. By Lemma 3.4, we have

$$\begin{aligned} R(H)=C(H-v_1)=C(P_{a_1})+C(P_{n-1-a_1})=2n-10+2^{2-a_1}+2^{3-n+a_1}. \end{aligned}$$

Note that . Let

It is easy to see that f(t) is strictly decreasing if $t\le \frac{n-1}{2}$ and strictly increasing if $t\ge \frac{n-1}{2}$. So f(t) is maximized at points $t=\lceil \frac{n-3}{3}\rceil$ or $n-3$. Let

Since and $f(n-3)=1+2^{5-n}$, we have

$$\begin{aligned} \theta _n={\left\{ \begin{array}{ll} -(1-2^{3-k})(1-2^{2-2k}) &{} \hbox {if }n=3k \hbox { with}\, k\ge 2,\\ -(1-2^{2-k})(1-2^{2-2k}) &{} \hbox {if } n=3k+1 \hbox { with}\, k\ge 2,\\ -(1-2^{2-k})(1-2^{1-2k}) &{} \hbox {if } n=3k+2 {\hbox { with}}\, k\ge 1. \end{array}\right. } \end{aligned}$$

This implies that

$$\begin{aligned} \theta _n {\left\{ \begin{array}{ll} >0 &{} \hbox {if } n=5,6,\\ =0 &{} \hbox {if } n=7,8,9,\\ <0 &{} \hbox {if } n\ge 10. \end{array}\right. } \end{aligned}$$

Correspondingly, we have three possibilities: (i) if $n=5,6$, then

$$\begin{aligned} R(H)=2n-10+2^{2-\lceil \frac{n-3}{3}\rceil }+2^{3-n+\lceil \frac{n-3}{3}\rceil } \end{aligned}$$

with $(a_1,a_2, a_3)=(1,1,0)$ when $n=5$ and $(a_1,a_2, a_3)=(1,1,1)$ when $n=6$; (ii) if $n=7,8,9$, then

$$\begin{aligned} R(H)=2n-10+1+2^{5-n}=2n-9+2^{5-n} \end{aligned}$$

with $a_1=n-3$ or $a_1=\lceil \frac{n-3}{3}\rceil$, that is, $(a_1, a_2, a_3)=(n-3, 0,0)$ or $(a_1, a_2, a_3)=(2,2,0), (2,1,1)$ when $n=7$, $(a_1, a_2, a_3)=(2,2,1)$ when $n=8$, and $(a_1, a_2, a_3)=(2,2,2)$ when $n=9$; (iii) if $n\ge 10$, then

$$\begin{aligned} R(H)=2n-10+1+2^{5-n}=2n-9+2^{5-n} \end{aligned}$$

with $a_1=n-3$, i.e., $(a_1, a_2, a_3)=(n-3, 0,0)$. Therefore, we have

$$\begin{aligned} R(H)= {\left\{ \begin{array}{ll} 2n-10+2^{2-\lceil \frac{n-3}{3}\rceil }+2^{3-n+\lceil \frac{n-3}{3}\rceil } &{} \hbox {if } n=5,6 \\ 2n-9+2^{5-n} &{} \hbox {if } n=4 {\hbox { or}}\, n\ge 7 \end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} (a_1,a_2, a_3)={\left\{ \begin{array}{ll} (n-3,0,0) &{} \hbox {if } \,n=4,\\ (1,1,0) &{} \hbox {if}\, n=5,\\ (1, 1,1) &{} \hbox {if } \,n=6,\\ (n-3, 0,0),(2,2,0), (2,1,1) &{} \hbox {if}\, n=7,\\ (n-3, 0,0), (2,2,1) &{} \hbox {if} \,n=8, \\ (n-3, 0,0),(2,2,2) &{} \hbox {if }\, n=9,\\ (n-3, 0,0) &{} \hbox {if}\, n\ge 10. \end{array}\right. } \end{aligned}$$

Now it suffices to show that $G=H$. Suppose to the contrary that G is a spanning subgraph of $H-e$ for some $e\in E(H)$. Since G is connected, e is not a cut edge of H. So e must be an edge in the block with three vertices. Therefore, $H-e$ is a tree and hence $G=H-e$. As G contains exactly $n-3$ cut vertices, G is not a path. By Lemmas 3.2 and 3.4, $H\ncong S(n-3,0,0), S(1,1,0), S(1,1,1), S(2,2,0), S(2,2,2)$. Let $v_i$ be the vertex in H at which the length of the pending path is $a_i$ for $i=1,2,3$. If $H\cong S(2,1,1)$, then $e\ne v_2v_3$ by Lemmas 3.2 and 3.4. However, $R(G)=R(H-v_1v_2)\le C(P_2)+C(P_3)=\frac{7}{2}<2\times 7-9+2^{5-7}=R(H)$, a contradiction. So, $H\ncong S(2,1,1)$. Similarly, if $H\cong S(2,2,1)$, then $e=v_1v_2$, so $R(G)=R(H-v_1v_2)\le 2C(P_3)=5<2\times 8-9+2^{5-8}=R(H)$, also a contradiction. It thus follows that $G=H$. $\square$

6 Proof of Theorem 2.3

Lemma 6.1

Let n, s and $a_1, \dots , a_s$ be nonnegative integers with $3\le s\le n-1$ and $\sum _{i=1}^s a_i =n-s$. Let $G=S(a_1,\dots , a_s)$. Then

$$\begin{aligned} C(G)=2n-6s+2s^2-2(s-2)\sum _{i=1}^s 2^{-a_i}-\sum _{i=1}^s 2^{-2a_i-1}+2^{-1}\left( \sum _{i=1}^s 2^{-a_i}\right) ^2. \end{aligned}$$

Moreover,

$$\begin{aligned}{} & {} C(G)\le 2n-6s+2s^2-2(s-2)(2s-p)2^{-t}\\ {}{} & {} +\left( \frac{p(p-1)}{2}+2(s-p)(s-1)\right) 2^{-2t} \end{aligned}$$

with equality if and only if $G\cong G_{n,n-s}$, where $n=ts+p$ with $0\le p\le s-1$.

Proof

Let $G=S(a_1,\dots , a_s)$. By direct calculation,

$$\begin{aligned} C(G)&=\sum _{i=1}^s C(P_{a_i+1})+\sum _{i=1}^s\sum _{j=0}^{a_i} \sum _{\begin{array}{c} k=1 \\ k\ne i \end{array}}^s\sum _{\ell =0}^{a_k} 2^{-(j+1+\ell )}\\&=\sum _{i=1}^s C(P_{a_i+1})+2^{-1}\sum _{i=1}^s\sum _{j=0}^{a_i} 2^{-j} \sum _{\begin{array}{c} k=1 \\ k\ne i \end{array}}^s\sum _{\ell =0}^{a_k} 2^{-\ell }\\&=2n-4s+\sum _{i=1}^s 2^{1-a_i}+2^{-1}\sum _{i=1}^s (2-2^{-a_i}) \sum _{\begin{array}{c} k=1 \\ k\ne i \end{array}}^s (2-2^{-a_{k}})\\&=2n-4s+\sum _{i=1}^s 2^{1-a_i}+2^{-1}\left( 4s^2-4s\sum _{i=1}^s 2^{-a_i}+\left( \sum _{i=1}^s 2^{-a_i}\right) ^2\right) \\&\quad -2^{-1}\sum _{i=1}^s \left( 4-2^{2-a_i}+2^{-2a_i}\right) \\&=2n-6s+2s^2-2(s-2)\sum _{i=1}^s 2^{-a_i}-\sum _{i=1}^s 2^{-2a_i-1}+2^{-1}\left( \sum _{i=1}^s 2^{-a_i}\right) ^2. \end{aligned}$$

Assume that $a_1\ge \dots \ge a_s$. If $a_1\ge a_s+2$, then by setting $G'=S(a_1-1,a_2,\dots ,a_{s-1},a_s+1)$, we have

$$\begin{aligned}&\quad C(G')-C(G)\\&=-2(s-2)\left( 2^{-(a_1-1)}+2^{-(a_s+1)}\right) -\left( 2^{-2(a_1-1)-1}+2^{-2(a_s+1)-1}\right) \\&\quad +2^{-1}\left( 2^{-2(a_1-1)}+2^{-2(a_s+1)}+2\sum _{i=2}^{s-1} 2^{-a_i}\left( 2^{-(a_1-1)}+2^{-(a_s+1)}\right) +2^{1-a_1-a_s}\right) \\&\quad +2(s-2)\left( 2^{-a_1}+2^{-a_s}\right) +\left( 2^{-2a_1-1}+2^{-2a_s-1}\right) \\&\quad -2^{-1}\left( 2^{-2a_1}+2^{-2a_s}+2\sum _{i=2}^{s-1} 2^{-a_i}\left( 2^{-a_1}+2^{-a_s}\right) +2^{1-a_1-a_s}\right) \\&=\left( 2s-4-\sum _{i=2}^{s-1}2^{-a_i}\right) \left( 2^{-a_s-1}-2^{-a_1}\right) \\&\ge (s-2)\left( 2^{-a_s-1}-2^{-a_1}\right) \\&>0, \end{aligned}$$

This shows that if G maximizes the residual closeness under the condition that $\sum _{i=1}^s a_i =n-s$, then $a_1-a_s\le 1$, that is, $G\cong G_{n,n-s}$. Recall that $n=ts+p$ with $0\le p\le s-1$. Then $a_i=t$ if $1\le i\le p$ and $a_i=t-1$ if $p+1\le i\le s$. So

$$\begin{aligned}&\quad C(G_{n,n-s})\\&=2n-6s+2s^2-2(s-2)\left( 2^{-t}p+(s-p)2^{1-t}\right) -2^{-2t-1}p\\&\quad -(s-p)2^{1-2t}+2^{-1}\left( p^22^{-2t}+2p(s-p)2^{1-2t}+(s-p)^22^{2-2t}\right) \\&=2n-6s+2s^2-2(s-2)(2s-p)2^{-t}+\left( \frac{p(p-1)}{2}+2(s-p)(s-1)\right) 2^{-2t}. \end{aligned}$$

This completes the proof. $\square$

Lemma 6.2

For positive integers n and r with $1\le r\le n-4$, let t and p be integers with $n=t(n-r)+p$ and $0\le p\le n-r-1$.

(i) If $p=0$, then

$$\begin{aligned} R(G_{n,r})&= 2(n-r-1)^2-4n+6r+2^{3-t}-4(n-r-1)(n-r-3)2^{-t}\\&\quad +2(n-r-1)(n-r-2)2^{-2t}. \end{aligned}$$

(ii) If $1\le p\le n-r-1$, then

$$\begin{aligned} R(G_{n,r})&= 2(n-r-1)^2-4n+6r+2^{2-t}-2(n-r-3)(2n-2r-p-1)2^{-t}\\&\quad +\left( \frac{(p-1)(p-2)}{2}+2(n-r-p)(n-r-2)\right) 2^{-2t}. \end{aligned}$$

Proof

Let $G_{n,r}=S(a_1,\dots ,a_{n-r})$, where $a_1\ge \dots \ge a_{n-r}\ge 0$. Evidently, $a_1>0$. Let $v_1$ be the vertex such that there is a pending path of length $a_1$. By Lemma 3.4,

$$\begin{aligned} R(G_{n,r})=C(G_{n,r}-v_1)=C(P_{a_1})+C(S(a_2,\dots ,a_{n-r})). \end{aligned}$$

If $p=0$, then $a_1=\dots =a_{n-r}=t-1$, so $S(a_2,\dots ,a_{n-r})=G_{n-t,r-t+1}$, and we have by Lemma 6.1 that

$$\begin{aligned} R(G_{n,r})&=C(P_{t-1})+C(G_{n-t,r-t+1})\\&=2(t-1)-4+2^{3-t}+2(n-t)-6(n-r-1)+ 2(n-r-1)^2\\&\quad -2(n-r-3)(2n-2r-2)2^{-t} +2(n-r-1)(n-r-2)2^{-2t}\\&=2(n-r-1)^2-4n+6r+2^{3-t}-4(n-r-1)(n-r-3)2^{-t}\\&\quad +2(n-r-1)(n-r-2)2^{-2t}. \end{aligned}$$

This proves (i).

If $1\le p\le n-r-1$, then $a_1=\dots =a_{p}=t$ and $a_{p+1}=\dots =a_{n-r}=t-1$, so $S(a_2,\dots ,a_{n-r})=G_{n-t-1, r-t}$, and we have by Lemma 6.1 that

$$\begin{aligned} R(G_{n,r})&=C(P_{t})+C(G_{n-t-1, r-t})\\&=2t-4+2^{2-t}+2(n-t-1)-6(n-r-1)+ 2(n-r-1)^2\\&\quad -2(n-r-3)(2(n-r-1)-(p-1))2^{-t}\\&\quad +\left( \frac{(p-1)(p-2)}{2}+2(n-r-1-(p-1))(n-r-1-1)\right) 2^{-2t}\\&=2(n-r-1)^2-4n+6r+2^{2-t}-2(n-r-3)(2n-2r-p-1)2^{-t}\\&\quad +\left( \frac{(p-1)(p-2)}{2}+2(n-r-p)(n-r-2)\right) 2^{-2t}. \end{aligned}$$

This proves (ii). $\square$

Lemma 6.3

For integers n and s with $4\le s\le n-1$, let

$$\begin{aligned} \mathcal {G}(n,s)=\left\{ S(a_1,\dots ,a_s): a_1\ge \dots \ge a_s\ge 0, \sum _{i=1}^s a_i+s=n\right\} . \end{aligned}$$

Then $G_{n,n-s}$ uniquely maximizes the residual closeness in $\mathcal {G}(n,s)$.

Proof

Suppose that G maximizes the residual closeness in $\mathcal {G}(n,s)$ with $G\ncong G_{n,n-s}$. Then $a_1\ge a_s+2$. Let j be the largest subscript with $a_1=a_j>a_{j+1}$ and k the smallest subscript with $a_1\ge a_k+2$. Let $Q_i$ be the pending path at $v_i$ and $u_i$ be the other terminal vertex of $Q_i$ for $i=j,k$. Denote by $u_j'$ the unique neighbor of $u_j$. Let $G'=G-u_j'u_j+u_ku_j$. By Lemma 3.4, $R(G')=C(G'-v_1)$.

If $j=1$, then, by setting $V_0=V(G)\setminus V(Q_1)$ and noting that $V(Q_k)\cup \{v_2,\dots ,v_s\}\subseteq V_0$, we have

$$\begin{aligned} R(G')-R(G)&=C(G'-v_1)-C(G-v_1)\\&=2\sum _{z\in V_0}2^{-d_{G'}(z,u_1)}-2\sum _{z\in V(Q_1)\setminus \{u_1,v_1\}}2^{-d_G(z,u_1)}\\&\ge 2\sum _{z\in V(Q_k)\cup \{v_2,\dots ,v_s\}}2^{-d_{G'}(z,u_1)}-2\sum _{z\in V(Q_1)\setminus \{u_1,v_1\}}2^{-d_G(z,u_1)}\\&=2\sum _{i=1}^{a_k+1}2^{-i}+2(s-2)2^{-a_k-2}-2\sum _{i=1}^{a_1-1}2^{-i}\\&=2-2^{-a_k}+(s-2)2^{-a_k-1}-2+2^{-a_1+2}\\&\ge 2^{-a_1+2}\\&>0, \end{aligned}$$

a contradiction.

Suppose that $j\ge 2$. Let $W=V(G){\setminus } (V(Q_1)\cup V(Q_j)\cup V(Q_k))$. Then

$$\begin{aligned} R(G')-R(G)&=C(G'-v_1)-C(G-v_1)\\&=2\sum _{w\in W} 2^{-d_{G'}(u_j,w)}-2\sum _{w\in W} 2^{-d_{G}(u_j,w)}\\&=2\sum _{w\in W} \left( 2^{-(a_k+1)-d_G(v_k,w)}-2^{-a_j-d_G(v_j,w)}\right) \\&=2\sum _{w\in W} 2^{-d_G(v_k,w)}\left( 2^{-(a_k+1)}-2^{-a_j}\right) \\&> 0, \end{aligned}$$

also a contradiction. So $G\cong G_{n,n-s}$. $\square$

Lemma 6.4

For nonnegative integers $t_1,t_2,t_3,t_4$ with $t_1\ge 2$,

$$\begin{aligned} C(P_{t_1})+C(S(t_2,t_3,t_4))< C(P_{t_1-1})+C(S(t_2+1,t_3,t_4)). \end{aligned}$$

Proof

It suffices to show that

$$\begin{aligned} C(P_{t_1})- C(P_{t_1-1})<C(S(t_2+1,t_3,t_4))-C(S(t_2,t_3,t_4)), \end{aligned}$$

i.e.,

$$\begin{aligned} 2\sum _{i=1}^{t_1-1}2^{-i}<2\left( \sum _{i=1}^{t_2+t_3+2}2^{-i}+2^{-t_2-2}\sum _{i=0}^{t_4}2^{-i}\right) , \end{aligned}$$

i.e.,

$$\begin{aligned} 1-2^{-t_1+1}<1-2^{-t_2-t_3-2}+2^{-t_2-2}(2-2^{-t_4}), \end{aligned}$$

i.e.,

$$\begin{aligned} 2^{-t_2-t_3-2}+2^{-t_2-t_4-2}<2^{-t_1+1}+2^{-t_2-1}. \end{aligned}$$

This is true trivially. $\square$

A block is nontrivial if it contains at least three vertices. For a clique graph G, denote by b(G) the number of nontrivial blocks in G.

Lemma 6.5

$G_{n,r}$ is the unique n-vertex clique graph with r cut vertices that maximizes the residual closeness, where $1\le r\le n-4$.

Proof

Suppose that H is an n-vertex clique graph with r cut vertices that maximizes the residual closeness.

We want to show that $b(H)=1$. Suppose to the contrary that $b(H)\ge 2$.

Case 1. $r=n-4$.

Let $n_1\ge \dots \ge n_{n-3}$ be the sizes of the blocks of H with $n_{n-3}\ge 2$. Then $n_1+\dots +n_{n-3}=n+n-4=2n-4$. As $n_2\ge 3$, we have $n_1=n_2=3$ and $n_3=\dots =n_{n-3}=2$. Let $B_0$ and $B_1$ be the two blocks of H with three vertices. Let $V(B_0)=\{u_0,w_1,w_2\}$ and $V(B_1)=\{u_1,w_3,w_4\}$. Assume that Q is the path connecting $u_0$ and $u_1$ in H. Then $G-E(B_0)\cup E(B_1)$ consists of vertex-disjoint paths Q, $Q_1,\dots , Q_4$, where $u_0, u_1\in V(Q)$, $w_i\in V(Q_i)$ for $i=1,\dots , 4$. Let s be the length of Q and $\ell _i$ be the length of $Q_i$ for $i=1,\dots , 4$. Evidently, $\sum _{i=1}^4\ell _i+s=n-5$.

Note that $G_{n, n-4}$ is an n-vertex clique graph with $n-4$ cut vertices and $b(G_{n, n-4})=1$. We will derive a contradiction by showing that $R(H)< R(G_{n, n-4})$. Let t and p be integers with $n=4t+p$ and $0\le p\le 3$. By Lemma 6.2, we have

$$\begin{aligned} R(G_{n,n-4})\ge 2n-6+12\cdot 2^{-2t}-8\cdot 2^{-t} \end{aligned}$$

(6.1)

as $t\ge 1$. Since $f(x)=12x^2-8x\ge f(\frac{1}{3})=-\frac{4}{3}$ for $x\in (0,\frac{1}{2}]$, one further has $R(G_{n,n-4})\ge 2n-6-\frac{4}{3}$.

If $s=0$, then $u_0=u_1$, so

$$\begin{aligned} R(H)\le C(G-u_0)&=C(P_{\ell _1+\ell _2+2})+C(P_{\ell _3+\ell _4+2})\\&=2(\ell _1+\ell _2+2)-4+2^{-\ell _1-\ell _2}+2(\ell _3+\ell _4+2)-4+2^{-\ell _3-\ell _4}\\&=2n-10+2^{-\ell _1-\ell _2}+2^{-\ell _3-\ell _4}\\&\le 2n-8\\&<R(G_{n.n-4}), \end{aligned}$$

which is a contradiction. So $s\ge 1$.

Assume that $\ell _4=\min \{\ell _i:1\le i\le 4\}$. Suppose that $t\le \ell _3+\ell _4+1$. If $p=0$, then $t\ge 2$, and we have by Lemmas 6.4 and 6.1 that

$$\begin{aligned} R(H)&\le C(H-u_1)\\&= C(P_{\ell _3+\ell _4+2})+C(S(s-1,\ell _1,\ell _2))\\&<C(P_{t-1})+C(S(s+\ell _3+\ell _4-t+2,\ell _1,\ell _2))\\&\le C(P_{t-1})+C(G_{n-t,n-t-3})\\&= R(G_{n,n-4}), \end{aligned}$$

a contradiction. If $p\ge 1$, then by Lemmas 6.4 and 6.1, we have

$$\begin{aligned} R(H)&\le C(H-u_1)\\&= C(P_{\ell _3+\ell _4+2})+C(S(s-1,\ell _1,\ell _2))\\&<C(P_{t})+C(S(s+\ell _3+\ell _4-t+1,\ell _1,\ell _2))\\&\le C(P_{t})+C(G_{n-t-1,n-t-4})\\&= R(G_{n,n-4}), \end{aligned}$$

also a contradiction. So $t\ge \ell _3+\ell _4+2$. It follows that $\ell _3\le t-2$. By Lemma 6.1 and Eq. (6.1),

$$\begin{aligned} R(H)&\le C(H-u_0)\\&=C(P_{\ell _1+\ell _2+2})+C(S(s-1,\ell _3,\ell _4))\\&=2(\ell _1+\ell _2)+2^{-\ell _1-\ell _2}+2(s+\ell _3+\ell _4+2)-2\left( 2^{-(s-1)}+2^{-\ell _3}+2^{-\ell _4}\right) \\&\quad -2^{-2(s-1)-1}-2^{-2\ell _3-1}-2^{-2\ell _4-1}+2^{-1}\left( 2^{-(s-1)}+2^{-\ell _3}+2^{-\ell _4}\right) ^2\\&=2n-6+2^{1-s}(2^{-\ell _3}-1)+2^{1-s}(2^{-\ell _4}-1)+2^{-\ell _1-\ell _2}+2^{-\ell _3-\ell _4}-2^{1-\ell _3}-2^{1-\ell _4}\\&\le 2n-6+2^{-\ell _4}+2^{-\ell _4}-2^{1-\ell _3}-2^{1-\ell _4}\\&= 2n-6-2^{1-\ell _3}\\&\le 2n-6-8\cdot 2^{-t}\\&<R(G_{n,n-4}), \end{aligned}$$

a contradiction. Therefore $b(H)=1$.

Case 2. $r\le n-5$.

By assumption, $b(H)\ge 2$. We call a nontrivial block B of H a pending block if for some vertex x in this block, the component of $H-E(B)$ containing x is a path (that may be trivial) with one end vertex being x. In this case, we call this path the path at x or the pending path at x if it is nontrivial. We choose a pending block $B_1$ so that for one of its vertex, say $u_0$, the length $\ell$ of the path at $u_0$ is minimum among paths at vertices of all pending blocks of H.

Denote by W the set of nontrivial blocks. As $b(H)\ge 2$, there is a nontrivial block $B_2\in W$ such that $t-1:=\min \{d_H(x,y): x\in V(B_1), y\in V(B_2)\}$ is the smallest among all blocks in W. Denote by $u_1\dots u_t$ the path connecting $u_1\in V(B_1)$ and $u_t\in V(B_2)$ in H.

For $w\in V(B_1)\cup V(B_2){\setminus }\{u_1, u_t\}$, denote by $T_w$ the component of $H-E(B_1)\cup E(B_2)$ containing w. Let $N=V(B_1){\setminus } \{u_0,u_1\}$. Let $V_0=V(T_{u_0})$, $V_1=\cup _{w\in N}V(T_w)$ and $V_2=\cup _{w\in V(B_2){\setminus } \{u_t\}}V(T_w)$. Let

$$\begin{aligned} H'=H-\{zu_0,zu_1:z\in N\}+\{zw:z\in N,w\in V(B_2)\}. \end{aligned}$$

Evidently, $H'$ is an n-vertex clique graph with r cut vertices, and $b(H')=b(H)-1$.

Claim 1. $R(H')\ge R(H)$ if $b(H)\ge 3$.

Suppose that $b(H)\ge 3$. Assume that $R(H')=C(H'-x)$ with $x\in V(H')$. By Lemma 3.3, $x\notin V_0\cup \{u_i:1\le i\le t-1\}$. As $b(H)\ge 3$, there is some vertex $y\in N\cup V(B_2){\setminus }\{u_t\}$ such that $T_y$ is not a path and hence there is some vertex $y'$ in $T_y$ of degree at least three. Let $V_0'=V_0\cup \{u_i:1\le i\le t\}$. Then

$$\begin{aligned} \sum _{z\in V(T_y)}2^{-d_{H'}(z,y)}\ge \sum _{i=0}^{d_{H'}(y,y')}2^{-i}+2^{-d_{H'}(y,y')}=2>2-2^{-\ell -t}=\sum _{z\in V_0'}2^{-d_{H'}(z,u_t)}. \end{aligned}$$

Let $V'=V(H')-V_0'-V(T_y)$. Then

$$\begin{aligned}&\quad C(H'-u_t)\\&=C(H')-2\sum _{z\in V_0'}\sum _{w\in V(H')\setminus V_0'}2^{-d_{H'}(z,w)}-2\sum _{z\in V_0'\setminus \{u_t\}}2^{-d_{H'}(z,u_t)}\\&=C(H')-2\sum _{z\in V_0'}2^{-d_{H'}(z,u_t)}\sum _{w\in V(H')\setminus V_0'}2^{-d_{H'}(u_t,w)}-2\sum _{z\in V_0'\setminus \{u_t\}}2^{-d_{H'}(z,u_t)}\\&=C(H')-2\sum _{z\in V_0'}2^{-d_{H'}(z,u_t)}\left( \sum _{w\in V'}2^{-d_{H'}(u_t,w)}+2^{-1}\sum _{w\in V(T_y)}2^{-d_{H'}(y,w)}+1\right) +2 \end{aligned}$$

and

$$\begin{aligned}&\quad C(H'-y)\\&=C(H')-2\sum _{z\in V(T_y)}\sum _{w\in V(H')\setminus V(T_y)}2^{-d_{H'}(z,w)}-2\sum _{z\in V(T_y)\setminus \{y\}}2^{-d_{H'}(z,y)}\\&=C(H')-2\sum _{z\in V(T_y)}2^{-d_{H'}(z,y)}\sum _{w\in V(H')\setminus V(T_y)}2^{-d_{H'}(y,w)}-2\sum _{z\in V(T_y)\setminus \{y\}}2^{-d_{H'}(z,y)}\\&=C(H')-2\sum _{z\in V(T_y)}2^{-d_{H'}(z,y)}\left( \sum _{w\in V'}2^{-d_{H'}(y,w)}+2^{-1}\sum _{w\in V_0'}2^{-d_{H'}(u_t,w)}+1\right) +2. \end{aligned}$$

Since

$$\begin{aligned} \sum _{w\in V'}2^{-d_{H'}(u_t,w)}=\sum _{w\in V'}2^{-d_{H'}(y,w)}, \end{aligned}$$

we have

$$\begin{aligned}&\quad C(H'-u_t)-C(H'-y)\\&=2\left( \sum _{w\in V'}2^{-d_{H'}(u_t,w)}+1\right) \left( \sum _{z\in V(T_y)}2^{-d_{H'}(z,y)}-\sum _{z\in V_0'}2^{-d_{H'}(z,u_t)} \right) \\&>0. \end{aligned}$$

So $x\ne u_t$ and $x\in V_1\cup V_2$.

As we pass from $H-x$ to $H'-x$, the distance between any pair of vertices in $V_0'\cup V_2$ and in $V_1$ remains unchanged. Moreover, for any $z\in V_1$,

$$\begin{aligned} \sum _{i=1}^t\left( 2^{-d_{H'-x}(z,u_i)}-2^{-d_{H-x}(z,u_i)}\right) =0. \end{aligned}$$

So

$$\begin{aligned} R(H')-R(H)\ge C(H'-x)-C(H-x)=2\sum _{z\in V_1}F(z) \end{aligned}$$

with

$$\begin{aligned} F(z)=\sum _{w\in V_0\cup V_2}\left( 2^{-d_{H'-x}(z,w)}-2^{-d_{H-x}(z,w)} \right) . \end{aligned}$$

By the definition of $\ell$ and the possibility that $x\in V(B_2)$, we have

$$\begin{aligned} \sum _{w\in V_2}2^{-d_{H-x}(u_t,w)}&=\sum _{v\in V(B_2)\setminus \{u_t\}}2^{-1}\sum _{w\in V(T_v)}2^{-d_{H-x}(v,w)}\\&\ge \sum _{v\in V(B_2)\setminus \{u_t\}}2^{-1}\sum _{i=0}^{\ell }2^{-i}\\&\ge (|V(B_2)|-2)(1-2^{-\ell -1})\\&\ge \sum _{w\in V_0}2^{-d_{H-x}(u_0,w)-1}. \end{aligned}$$

For any $z\in V_1$, we have

$$\begin{aligned} d_{H'-x}(z,w)=d_{H-x}(z,w){\left\{ \begin{array}{ll} +t&{}\hbox { if }w\in V_0,\\ -t&{}\hbox { if }w\in V_2, \end{array}\right. } \end{aligned}$$

so

$$\begin{aligned} F(z)&=(2^{-t}-1)\sum _{w\in V_0}2^{-d_{H-x}(z,w)}+(2^{t}-1)\sum _{w\in V_2}2^{-d_{H-x}(z,w)}\\&=(2-2^{-t+1})2^{-d_{H-x}(z,u_0)}\left( \sum _{w\in V_2}2^{-d_{H-x}(u_t,w)}-\sum _{w\in V_0}2^{-d_{H-x}(u_0,w)-1} \right) \\&\ge 0. \end{aligned}$$

Therefore $R(H')-R(H)=2\sum _{z\in V_1}F(z)\ge 0$. That is, $R(H')\ge R(H)$. This proves Claim 1.

By Claim 1 and the choice of H, we may assume that $b(H)=2$. Then $B_1$ and $B_2$ are the only two nontrivial blocks in H. As $r\le n-5$, we have $(|V(B_1)|, |V(B_2)|)\ne (3,3)$. Assume that $|V(B_1)|\le |V(B_2)|$ if there is also a pending path of length $\ell$ at some vertex in $B_2$. By the definition of $\ell$,

$$\begin{aligned} \sum _{w\in V(T_v)}2^{-d_{H}(v,w)}\ge \sum _{w\in V_0}2^{-d_{H}(v_0,w)}=2-2^{-\ell } \end{aligned}$$

(6.2)

for $v\in N\cup V(B_2)\setminus \{u_t \}$.

Assume that $R(H')=C(H'-x)$ for some $x\in V(H')$. By Lemma 3.3, $x\in N\cup V(B_2)$. As we pass from $H-x$ to $H'-x$, the distance between any pair of vertices in $V_0\cup V_2\cup \{u_i:1\le i\le t\}$ and in $V_1$ remains unchanged. Then

$$\begin{aligned} R(H')-R(H)\ge C(H'-x)-C(H-x)=2\sum _{z\in V_1}F(z) \end{aligned}$$

with

$$\begin{aligned} F(z)=\sum _{w\in V_0\cup V_2\cup \{u_i:1\le i\le t\}}\left( 2^{-d_{H'-x}(z,w)}-2^{-d_{H-x}(z,w)}\right) . \end{aligned}$$

Suppose that $x\in V(B_2)\setminus \{u_t\}$, or $x\in N$ with $|N|\ge 2$. For any $z\in V_1$, we have

$$\begin{aligned} \sum _{i=1}^t\left( 2^{-d_{H'-x}(z,u_i)}-2^{-d_{H-x}(z,u_i)}\right) =0, \end{aligned}$$

so

$$\begin{aligned} F(z)=\sum _{w\in V_0\cup V_2}\left( 2^{-d_{H'-x}(z,w)}-2^{-d_{H-x}(z,w)} \right) . \end{aligned}$$

Note that, for any $z\in V_1$,

$$\begin{aligned} d_{H'-x}(z,w)=d_{H-x}(z,w){\left\{ \begin{array}{ll} +t&{}\hbox { if }w\in V_0,\\ -t&{}\hbox { if }w\in V_2, \end{array}\right. } \end{aligned}$$

so

$$\begin{aligned} F(z)&=(2^{t}-1)\sum _{w\in V_2}2^{-d_{H-x}(z,w)}+(2^{-t}-1)\sum _{w\in V_0}2^{-d_{H-x}(z,w)}\\&=(2-2^{-t+1})2^{-d_{H-x}(z,u_0)}\left( \sum _{w\in V_2}2^{-d_{H-x}(u_t,w)}-\sum _{w\in V_0}2^{-d_{H-x}(u_0,w)-1}\right) . \end{aligned}$$

If $|V(B_2)|=3$, then any pending path at vertices in $B_2$ is of length at least $\ell +1$ and hence

$$\begin{aligned} \sum _{w\in V_2}2^{-d_{H-x}(u_t,w)}-\sum _{w\in V_0}2^{-d_{H-x}(u_0,w)-1}\ge 1-2^{-\ell -2}-(1-2^{-\ell -1})>0. \end{aligned}$$

If $|V(B_2)|\ge 4$, then

$$\begin{aligned} \sum _{w\in V_2}2^{-d_{H-x}(u_t,w)}-\sum _{w\in V_0}2^{-d_{H-x}(u_0,w)-1}\ge 2(1-2^{-\ell -1})-(1-2^{-\ell -1})>0. \end{aligned}$$

So, if $z\notin V(T_x)$, then $d_{H-x}(z,u_0)$ is finite, so $F(z)>0$. If $z\in V(T_x)$, then $d_{H-x}(z,u_0)=\infty$, so $F(z)=0$. Since $x\in V(B_2){\setminus }\{u_t\}$ or $x\in N$ with $|N|\ge 2$, $V_1\setminus V(T_x)\ne \emptyset$. Therefore, $R(H')-R(H)=2\sum _{z\in V_1}F(z)>0$, a contradiction. It thus follows that $x=u_t$ or $N=\{x\}$.

Suppose that $x=u_t$. If $|V(B_2)|\ge 4$, then

$$\begin{aligned} F(z)=\sum _{w\in V_2}2^{-d_{H'}(z,w)}-\sum _{w\in V_0\cup \{u_i:1\le i\le t-1\}}2^{-d_{H}(z,w)}. \end{aligned}$$

For any $z\in V_1$ ($w\in V_2$, respectively), there exists a vertex $u\in N$ ($v\in V(B_2)\setminus \{u_t\}$, respectively) such that $z\in V(T_u)$ ($w\in V(T_v)$, respectively). Then by Eq. (6.2),

$$\begin{aligned} F(z)&=\sum _{w\in V_2}2^{-d_{H'}(z,w)}-\sum _{w\in V_0\cup \{u_i:1\le i\le t-1\}}2^{-d_{H}(z,w)}\\&=2^{-d_{H}(z,u)-1}\left( \sum _{v\in V(B_2)\setminus \{u_t\}}\sum _{w\in V(T_v)}2^{-d_{H}(v,w)}\right. \\&\quad \left. -\sum _{w\in V_0}2^{-d_{H}(u_0,w)}-\sum _{w\in \{u_i:1\le i\le t-1\}}2^{-d_{H}(u_1,w)}\right) \\&\ge 2^{-d_{H}(z,u)-1}\left( (|V(B_2)|-1)(2-2^{-\ell })-(2-2^{-\ell }) -(2-2^{-t+1})\right) \\&\ge 2^{-d_{H}(z,u)-1}\left( 2-2^{1-\ell }+2^{-t+1}\right) \\&>0 \end{aligned}$$

and hence $R(H')-R(H)>0$, a contradiction. So $|V(B_2)|=3$. As $r\le n-5$, $|V(B_1)|\ge 4$. As we pass from $H-u_1$ to $H'-u_t$, the distance between any pair of vertices in $V_0$, in $V_1$ and in $V_2$ remains unchanged. So

$$\begin{aligned}&\quad C(H'-u_t)-C(H-u_1)\\&=2\sum _{z\in V_1}\sum _{w\in V_2}2^{-d_{H'}(z,w)}-2\sum _{z\in V_1}\sum _{w\in V_0}2^{-d_H(z,w)}\\&\quad +2\sum _{i=1}^{t-1}\sum _{w\in V_0}2^{-d_{H'}(u_i,w)}-2\sum _{i=2}^{t}\sum _{w\in V_2}2^{-d_H(u_i,w)}. \end{aligned}$$

For any $z\in V_1$ and $w\in V_2$, we have

$$\begin{aligned} d_{H'}(z,w)=d_{H}(z,u_0)+d_{H}(u_t,w)-1, \end{aligned}$$

so

$$\begin{aligned} \sum _{z\in V_1}\sum _{w\in V_2}2^{-d_{H'}(z,w)}=\sum _{z\in V_1}2^{-d_{H}(z,u_0)}\sum _{w\in V_2}2^{-d_{H}(w,u_t)+1}. \end{aligned}$$

Moreover, we have

$$\begin{aligned} \sum _{z\in V_1}\sum _{w\in V_0}2^{-d_H(z,w)}=\sum _{z\in V_1}2^{-d_H(z,u_0)}\sum _{w\in V_0}2^{-d_H(u_0,w)}=(2-2^{-\ell })\sum _{z\in V_1}2^{-d_H(z,u_0)}, \\ \sum _{i=1}^{t-1}\sum _{w\in V_0}2^{-d_{H'}(u_i,w)}=\sum _{i=1}^{t-1}2^{-i}\sum _{w\in V_0}2^{-d_{H}(u_0,w)}=(1-2^{-t+1})(2-2^{-\ell }) \end{aligned}$$

and

$$\begin{aligned} \sum _{i=2}^{t}\sum _{w\in V_2}2^{-d_H(u_i,w)}=\sum _{i=1}^{t-1}2^{-i}\sum _{w\in V_2}2^{-d_H(u_t,w)+1}=(1-2^{-t+1})\sum _{w\in V_2}2^{-d_H(u_t,w)+1}. \end{aligned}$$

Therefore

$$\begin{aligned}&\quad C(H'-u_t)-C(H-u_1)\\&=2\sum _{z\in V_1}2^{-d_H(z,u_0)}\left( \sum _{w\in V_2}2^{-d_H(u_t,w)+1}-2+2^{-\ell } \right) \\&\quad +2(1-2^{-t+1})\left( 2-2^{-\ell }-\sum _{w\in V_2}2^{-d_H(u_t,w)+1}\right) \\&=2\left( \sum _{z\in V_1}2^{-d_H(z,u_0)}-1+2^{-t+1} \right) \left( \sum _{w\in V_2}2^{-d_H(u_t,w)+1}-2+2^{-\ell } \right) \\&>0, \end{aligned}$$

where the strict inequality follows as $|V(B_1)|\ge 4$. Therefore, $R(H')=C(H'-u_t)> C(H-u_1)\ge R(H)$, a contradiction. This means that $N=\{x\}$, so $V(B_1)=\{u_0,u_1,x\}$ and $V_1=V(T_x)$.

As we pass from $H-u_1$ to $H'-x$, the distance between any pair of vertices in $V_0$, in $V_1{\setminus }\{x\}$ and in $V_2\cup \{u_i:2\le i\le t\}$ remains unchanged. Note that

$$\begin{aligned} \sum _{w\in V_2\cup \{u_2,\dots ,u_t\}}2^{-d_{H}(u_1,w)}\ge \sum _{i=1}^{t-1}2^{-i}+\left( |V(B_2)|-1\right) 2^{-t}\ge 1 \end{aligned}$$

and

$$\begin{aligned} \sum _{w\in V(T_x)\setminus \{x\}}2^{-d_{H}(x,w)}=\sum _{i=1}^{\ell '}2^{-i}<1 \end{aligned}$$

where $\ell '$ is the length of path $T_x$. So

$$\begin{aligned} \quad R(H')-R(H)&\ge C(H'-x)-C(H-u_1)\\&=2\sum _{z\in V_0\cup \{u_1\}}\sum _{w\in V_2\cup \{u_2,\dots ,u_t\}}2^{-d_{H'}(z,w)}\\&\quad -2\sum _{z\in V_0\cup \{x\}}\sum _{w\in V(T_x)\setminus \{x\}}2^{-d_{H}(z,w)}\\&=2\sum _{z\in V_0\cup \{u_1\}}2^{-d_{H}(z,u_1)}\sum _{w\in V_2\cup \{u_2,\dots ,u_t\}}2^{-d_{H}(u_1,w)}\\&\quad -2\sum _{z\in V_0\cup \{x\}}2^{-d_{H}(z,x)} \sum _{w\in V(T_x)\setminus \{x\}}2^{-d_{H}(x,w)}\\&=\left( 4-2^{-\ell }\right) \left( \sum _{w\in V_2\cup \{u_2,\dots ,u_t\}}2^{-d_{H}(u_1,w)}-\sum _{w\in V(T_x)\setminus \{x\}}2^{-d_{H}(x,w)}\right) \\&>0, \end{aligned}$$

a contradiction. It follows that $b(H)=1$.

By combining Cases 1 and 2, we have $b(H)=1$ for $1\le r\le n-4$. By Lemma 6.3, $H\cong G_{n,r}$. $\square$

Now we are ready to prove Theorem 2.3.

Proof of Theorem 2.3

Let G be a graph with maximum residual closeness among all n-vertex connected graphs with r cut vertices.

By Lemma 3.2, $R(G)=R(H)$, and G is a spanning subgraph of H, which is obtained from G by adding all possible edges such that any cut vertex of G is still a cut vertex of H. So H is an n-vertex clique graph with r cut vertices. By Lemma 6.5, $H\cong G_{n,r}$. By Lemma 6.2,

$$\begin{aligned} R(G)&= 2(n-r-1)^2-4n+6r+2^{3-t}-4(n-r-1)(n-r-3)2^{-t}\\&\quad +2(n-r-1)(n-r-2)2^{-2t} \end{aligned}$$

if $p=0$, and

$$\begin{aligned} R(G)&= 2(n-r-1)^2-4n+6r+2^{2-t}-2(n-r-3)(2n-2r-p-1)2^{-t}\\&\quad +\left( \frac{(p-1)(p-2)}{2}+2(n-r-p)(n-r-2)\right) 2^{-2t} \end{aligned}$$

otherwise.

Denote by B the unique block of H of size $n-r$. It is easy to see that any edge of H outside B is also an edge of G.

Case 1. $p\ne 1,2$.

There are at least three longest pending paths in H. Take an arbitrary $e\in E(B)$ of H. There is at least one vertex, say x that is not incident to e and there is a longest pending path at x in H. By Lemma 3.4, $R(H)=C(H-x)$. By Lemma 3.2, $R(H-e)<R(H)$. Therefore $G=H$.

Case 2. $p=1$.

By Lemma 3.4, $R(H)=C(H-v)$, where v is the vertex in B at which there is a longest pending path in H. Suppose that $G\ne H$. By Lemma 3.2, $G= H-E_1$, where $E_1$ is a subset of edges of B that is incident to v. By Lemma 3.4, $R(H)=C(H-v)<C(H-x)$ for any $x\in V(H)\setminus \{v\}$. Let $\ell =|E_1|$. Then $G=H-E_1$ with $\ell \le n-r-2$ as otherwise $H-E_1$ is not connected. Let $u\in N_G(v)\cap V(B)$. If $\ell =n-r-2$, then v is on the pending path at u in G. By Lemma 3.3, $C(G-v)>C(G-u)$ and hence $R(H)=C(H-v)=C(G-v)>C(G-u)\ge R(G)$, a contradiction. It thus follows that $\ell \le n-r-3$.

By Lemma 3.3, we have $R(G)=C(G-x)$ for some $x\in V(B)$. For any $w\in N_H(v)\setminus N_G(v)$, $G-u$ is a proper subgraph of $G-w$ and hence $C(G-w)>C(G-u)$ by Lemma 3.1. Then $R(G)=\min \{C(G-v),C(G-u)\}$ by Lemma 3.4. However, $R(G)\le C(G-v)=C(H-v)=R(H)$ and $R(G)=R(H)$. So $R(G)=C(G-v)\le C(G-u)$. Let Q and $Q'$ the pending paths at v and u, respectively. Let $V'=V(G)\setminus (V(Q)\cup V(Q'))$. As we pass from $G-v$ to $G-u$, the distance between any pair of vertices in $V'$ remains unchanged. So

$$\begin{aligned} 0&\ge C(G-v)-C(G-u)\\&=2\sum _{x\in V(Q')}\sum _{z\in V'}2^{-d_G(x,z)}-2\sum _{x\in V(Q)}\sum _{z\in V'}2^{-d_G(x,z)}\\&\quad +2\sum _{x\in V(Q')\setminus \{u\}}2^{-d_{G}(x,u)}-2\sum _{x\in V(Q)\setminus \{v\}}2^{-d_{G}(x,v)}\\&=2\sum _{x\in V(Q')}2^{-d_G(x,u)} \sum _{z\in V'}2^{-d_G(u,z)}-2\sum _{x\in V(Q)}2^{-d_G(x,v)}\sum _{z\in V'}2^{-d_G(v,z)}\\&\quad +2\sum _{i=1}^{t-1}2^{-i}-2\sum _{i=1}^t2^{-i}\\&=2\left( \ell \left( \sum _{i=0}^{t-1}2^{-i}\sum _{i=1}^{t}2^{-i}-\sum _{i=0}^{t}2^{-i}\sum _{i=2}^{t+1}2^{-i}\right) -2^{-t-1}\left( n-r-\ell -2\right) \sum _{i=0}^{t-1}2^{-i}-2^{-t}\right) \\&=2\left( \ell \left( 1-3\times 2^{-t-1}+2^{-2t-1}\right) -(n-r-2)\left( 2^{-t}-2^{-2t}\right) -2^{-t}\right) . \end{aligned}$$

It follows that

$$\begin{aligned} \ell \le \frac{(n-r-2)\left( 2^{-t}-2^{-2t}\right) +2^{-t}}{1-3\times 2^{-t-1}+2^{-2t-1}}, \end{aligned}$$

i.e.,

$$\begin{aligned} \ell \le \frac{(n-r-2)\left( 2^{t+1}-2\right) +2^{t+1}}{2^{2t+1}-3\times 2^{t}+1}. \end{aligned}$$

So $\ell$ satisfies (2.1). Conversely, if $\ell =|E_1|$ satisfies (2.1), then it is easy to see that $C(H-E_1-v)\le C(H-E_1-u)$, so $R(H-E_1)=C(H-E_1-v)=C(H-v)=R(H)$.

Case 3. $p=2$.

Suppose that $G\ne H$. Let $v_1$ and $v_2$ be the only two vertices with pending paths of length t in H. Take any $e\in E(B)$ with $e\ne v_1v_2$. One of $v_1$ and $v_2$, say $v_2$, is not incident to e. By Lemma 3.4, $R(H)=C(H-v_2)$, so $R(H)-R(H-e)\ge C(H-v_2)-C(H-e-v_2)>0$, i.e., $R(H)>R(H-e)$. This shows that $G= H-v_1v_2$.

By Lemma 3.3, $C(G-x)>R(G)$ for any $x\in V(G){\setminus } V(B)$. Let $v_3\in V(B){\setminus } \{v_1,v_2\}$. So $R(G)=\min \{C(G-v_1), C(G-v_3)\}$.

Denote by $Q_i$ the pending path at $v_i$ in G for $i=1,3$. Let $V''=V(G)\setminus (V(Q_1)\cup V(Q_3))$. Then

$$\begin{aligned}&\quad C(G-v_1)-C(G-v_3)\\&=2\sum _{x\in V(Q_3)}\sum _{z\in V''}2^{-d_{G}(x,z)}-2\sum _{x\in V(Q_1)}\sum _{z\in V''}2^{-d_{G}(x,z)}\\&\quad +2\sum _{x\in V(Q_3)\setminus \{v_3\}}2^{-d_G(x,v_3)}-2\sum _{x\in V(Q_1)\setminus \{v_1\}}2^{-d_G(x,v_1)}\\&=2\sum _{x\in V(Q_3)}2^{-d_{G}(x,v_3)} \sum _{z\in V''}2^{-d_{G}(v_3,z)} -2\sum _{x\in V(Q_1)}2^{-d_{G}(x,v_1)} \sum _{z\in V''}2^{-d_{G}(v_1,z)}\\&\quad +2\sum _{i=1}^{t-1}2^{-i}-2\sum _{i=1}^{t}2^{-i}\\&=2\left( \sum _{i=0}^{t-1}2^{-i}\sum _{i=1}^{t+1}2^{-i}-\sum _{i=0}^{t}2^{-i}\sum _{i=2}^{t+2}2^{-i} -(n-r-3)2^{-t-1}\sum _{i=0}^{t-1}2^{-i}-2^{-t}\right) \\&=2\left( 1-3\times \left( 2^{-t}-2^{-2t-2}\right) -(n-r-3)\left( 2^{-t}-2^{-2t}\right) \right) . \end{aligned}$$

Note that $R(G)\le C(G-v_1)=C(H-v_1)=R(H)$. As $R(G)=R(H)$, we have $C(G-v_1)\le C(G-v_3)$, that is,

$$\begin{aligned} 2\left( 1-3\times \left( 2^{-t}-2^{-2t-2}\right) -(n-r-3)\left( 2^{-t}-2^{-2t}\right) \right) \le 0, \end{aligned}$$

or equivalently, $n-r\ge \frac{2^{2t+2}-9}{2^{t+2}-4}$. Conversely, if $n-r\ge \frac{2^{2t+2}-9}{2^{t+2}-4}$, then $R(H-v_1v_2)=C(H-v_1v_2-v_1)=R(H)$. Thus, $G=H-v_1v_2$ if $n-r\ge \frac{2^{2t+2}-9}{2^{t+2}-4}$ and $G=H$ otherwise.

By combining Cases 1–3, we conclude that

$$\begin{aligned} G\cong {\left\{ \begin{array}{ll} G_{n,r}, G_{n,r,\ell } &{} ~\textit{if}~p=1 ~\textit{and} ~\ell ~~\textit{satisfies}~~(2.1),\\ G_{n,r}, G_{n,r}^- &{} ~\textit{if}~p=2 ~\textit{and} ~ n-r\ge \frac{2^{2t+2}-9}{2^{t+2}-4},\\ G_{n,r} &{} \textit{otherwise}. \end{array}\right. } \end{aligned}$$

This completes the proof. $\square$