The Hitting Times of Random Walks on Bicyclic Graphs

Abstract

Let $H_G(x, y)$ be the expected hitting time from vertex x to vertex y for the first time on a simple connected graph G and $\varphi (G){:}{=}\max \left\{ H_G(x, y): x, y\in V(G)\right\}$ be called the hitting time of G. In this paper, sharp upper and lower bounds for $\varphi (G)$ among all n-vertex bicyclic graphs are presented and the extremal graphs are determined.

1 Introduction

Random walks on graphs have been extensively studied. The theory of random walk is closely related to other branches of graph theory such as spectra of graphs and electrical resistances of graphs. The hitting time, cover time, mixing time, commute time are key parameters of random walks on graphs [1, 7, 15, 16, 20, 22, 23]. Lovász [21] published an excellent survey about the connection between random walks on undirected graphs and eigenvalues, electrical networks. Doyle and Snell [12] wrote a comprehensive book on electrical networks, which is the basis for studying random walks on graphs and electrical networks. Effective resistance is a significant parameter of electrical networks, Tetali [26], Klein and Randi$\acute{c}$ [18] established a intertwined relationship between effective resistance and random walks on graphs. Georgakopoulos and Wagner [13] exhibited a subtle connection among the hitting time, the cover cost and the Wiener index on trees. Kirkland and Neumann [19] provided an explicit formula for the hitting times on graphs while there is a cut vertex in the graph from the perspective of matrix theory [17, 25]. Cogill and Peng [11] gave a method for computing an upper bound on hitting time from spanning tree of the graph. Moreover, spanning tree method is a crucial measure to study the hitting times on graphs. Chung and Yau [10] proved the explicit formula of hitting time on the basis of the discrete Green’s function. Chang and Xu [6, 27, 28] derived some new explicit formulas of hitting times for random walks on graphs in terms of enumerations of spanning trees and the discrete Green’s function. From the perspective of graph structure, Chen and Zhang [8, 9] and Huang and Li [14] gave explicit formulas of the hitting times for simple random walks on special graphs such as trees, unicyclic graphs, subdivision and triangulation graphs, quadrilateral graphs.

Furthermore, Brightwell and Winkler [5] proved that the n-vertex lollipop graph G and vertices x and y for which $H_G(x, y)$ is maximized among all n-vertex graphs. The extremal graph consists of a clique on $\left\lfloor \frac{(2n+1)}{3}\right\rfloor$ $\left({\rm or}\left\lfloor \frac{(2n-2)}{3}\right\rfloor \right)$ vertices, including x, to which a path on the remaining vertices, ending in y, has been attached. Then $\varphi (G)$ in this graph is approximately $\frac{4n^3}{27}$. Thus, if vertex number of graph is fixed, then the extremal graphs are determined. The results motivate us to propose the following general problem considering the fixed vertex number and edge number.

Question 1.1

Let ${\mathcal {G}}_{n, m}$ be set of all simple connected graphs with n vertices and m edges. What are the sharp upper and lower bounds for hitting times of graphs in ${\mathcal {G}}_{n, m}$. Furthermore, how to characterise all extremal graphs which attain these values?

Zhang and Li [29] determined the sharp upper and lower bounds on $\varphi (G)$ for $G\in {\mathcal {G}}_{n, n-1}$, and they showed that the n-vertex star $S_n$ attains the lower bound, and the n-vertex path $P_n$ attains the upper bound. Moreover, Zhu and Zhang [30] gave the sharp upper and lower bounds for hitting times of graphs in ${\mathcal {G}}_{n, n}$ and determined the extremal graphs.

In this paper, we continue to make some contributions to this problem. First we study the relationship between the hitting times of graphs and the hitting times of subgraphs. The results are used to present sharp upper and lower bounds for the hitting times of n-vertex bicyclic graphs. Moreover, we will characterize all extremal graphs which attain the upper and lower bounds. The main result is stated as follows:

Theorem 1.2

Let G be any n-vertex bicyclic connected graph. If $n\ge 12,$ then

$$\begin{aligned} 2n+3\le \varphi (G)\le n^2+2n-19. \end{aligned}$$

Moreover, the left equality holds if and only if G is a graph obtained by identifying the center of $K_{1, n-5}$ and the common vertex of two triangles without sharing edge, and $\varphi (G)$ is equal to the hitting time from a vertex with degree 2 in triangle to a pendant vertex. The right equality holds if and only if G is a graph obtained by identifying an end of a path on $(n-3)$ vertices and a vertex with degree 2 in $K_4-e$, where $K_4-e$ is a graph obtained by deleting one edge from complete graph $K_4$, and $\varphi (G)$ is equal to the hitting time from the furthest vertex from the pendant vertex to the pendant vertex.

The rest of this paper is arranged as follows. In Sect. 2, we present symbols and some key results which will be used to prove the main results. In Sect. 3, we focus on the extremal problem of hitting times of all n-vertex bicyclic graphs which composed of two cycles joined by a path and in which a (possibly empty) tree is attached to each vertex. In Sect. 4, we concentrate on the extremal problem of hitting times of all n-vertex bicyclic graphs which composed of three internally disjoint paths with common end vertices and in which a (possibly empty) tree is attached to each vertex. In Sect. 5, we give the proof of Theorem 1.2 and some remarks.

2 Preliminary

First of all, we introduce some symbols and notations. A simple random walk on a graph is a walk from any vertex of a graph to its adjacent vertices with equal probability. Let G be a simple (without loops and multiedges) connected graph with vertex set V(G) and edge set E(G). The distance between vertices u and v in G is denoted by $dist_G(u, v)$, or dist(u, v) for short. The expected hitting time $H_G(x, y)$ is the expected number of steps it takes a simple random walk on a graph G from a vertex x to vertex y for the first time. If $M\subseteq V(G)$, then $H_G(x, M)$ is the expected hitting time from vertex x to reach a vertex in M for the first time. It does not matter which the vertex is, but it must be the first vertex in M to be hit. If $x\in M$, then $H_G(x, M)=0$. The first return time $H_G^{+}(y, y)$ is the expected number of steps it takes a simple random walk on a graph G starts from vertex y and then first return to y, which is different from $H_G(y, y)=0$. For a given graph G, the hitting time of G is defined to be

$$\begin{aligned} \varphi (G)=\max \{H_G(x, y): x,y\in V(G)\}. \end{aligned}$$

Let ${\mathcal {G}}_n$ be a subset of the set of all n-vertex simple connected graphs. Let $\phi (n){:}{=}\max \{\varphi (G):G\in {\mathcal {G}}_n\}$ and $\psi (n) {:}{=}\min \{\varphi (G):G\in {\mathcal {G}}_n\}$. If there is a graph G such that $\varphi (G)=\phi (n)$ (resp. $\varphi (G)=\psi (n)$), then G is called an n-maximal (resp. n-minimal) graph for ${\mathcal {G}}_n$.

Let $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ be two simple connected graphs such that $V_1\cap V_2=\{x, y\}$ and $E_1\cap E_2=\emptyset$. The graph $G=G_1\cup G_2$ is union of two graphs $G_1$ and $G_2$, i.e., defined by $V(G)=V_1\cup V_2$ and $E(G)=E_1\cup E_2$. In that case, G is said to be decomposed into $G_1$ and $G_2$ through x and y. $G_1$, $G_2$ are regarded as a decomposition of G through x and y. The effective resistance R(x, y) between x and y can be defined in terms of the potential difference between x and y when a unit current from x to y is maintained. While G is treated as an electrical network and each edge of G is replaced with a unit resistor, $R_G(x, y)$ is the effective resistance between x and y in G by Ohm’s law. Let N[v] be the induced subgraph of G induced by v and all vertices adjacent to v. Let N(v) be the neighbour set of vertex v.

A bicyclic graph is a connected graph where edge number equals one plus the vertex number, its cyclomatic number is 2. It is easy to see that any bicyclic graph contains two cycles, which have either no common edges or at least one common edge. We denote the set of all connected n-vertex bicyclic graphs by ${\mathcal {B}}(n)$ and ${\mathcal {B}}(n)={\mathcal {B}}_1(n)\cup {\mathcal {B}}_2(n)$, where ${\mathcal {B}}_1(n)$ is the set of all n-vertex bicyclic graphs whose cycles have no common edges and ${\mathcal {B}}_2(n)$ is the set of all n-vertex bicyclic graphs whose cycles have at least one common edge (see Fig. 1).

If $G\in {\mathcal {B}}_1(n)$, then G has two edge disjoint cycles $C_p$ and $C_q$. Without loss of generality, we may assume that G can be obtained from two cycles $C_p=u_1u_2\ldots u_p$ and $C_q=v_1v_2\ldots v_q$ joined by a $u_1v_1$-path (possibly the length of path is 0) $P=u_1w_0w_1\ldots w_{m-1}v_1$ and in which trees $T_{u_i}$ $(1\le i\le p)$, $T_{v_j}$ $(1\le j\le q)$ and $T_{w_k}$ $(0\le k\le m-1)$ are attached to $u_i$, $v_j$ and $w_k$, respectively. G can be denoted by $G{:}{=}B(T_{u_1}, \ldots , T_{u_p}, T_{w_0}, \ldots , T_{w_{m-1}}, T_{v_1}, \ldots , T_{v_q})$ (see Fig. 1). In particular, if $u_1$, $w_0$ and $v_1$ are coincident, i.e., the length of P is 0, then we denote the common vertex of two cycles by $u_1$; if the length of P is 1, then $P=u_1v_1$. Moreover, let $P^{p, q}_n$ be the graph consisting of two cycles $C_p$ and $C_q$ with a common vertex $u_1$ (i.e., $V(C_p)\cap V(C_q)=u_1$) and the path of length $(n+1-p-q)$ is attached to the vertex $v_i$ of $C_q$, where the path is rooted at $v_i$ and the distance between $u_1$ and $v_i$ is $\lfloor \frac{q}{2}\rfloor$ (see Fig. 2). Let $S_n^{p, q}$ be the graph obtained by identifying the unique common vertex of $C_p$ and $C_q$ and center of the $(n+2-p-q)$-vertex star $K_{1, n+1-p-q}$ (see Fig. 2). In particular, if $p=q=3$, then we denote $P^{3, 3}_n$ by $B_1^{*}(n)$ and denote $S_n^{3, 3}$ by $B_1^{\sharp }(n)$.

If $G\in {\mathcal {B}}_2(n)$, then there are two cycles having common edges in G, i.e., there are three internally disjoint paths with common end vertices in G. Without loss of generality, we assume that G has three internally disjoint paths $P_p{:}{=}xu_1u_2\ldots u_py,$ $P_q{:}{=}xv_1\ldots v_{q}y$ and $P_{m}{:}{=} xw_1\ldots w_{m}y$ with common end vertices x, y, where $p\ge q\ge m$ and $m\ge 0$. Moreover, if $m=0$, then $P_m=xy$. Hence, G can be obtained from $P_p, P_q, P_m$ by attaching the trees $T_{u_i}$ ($1\le i \le p$), $T_{v_j}$ ($1 \le j \le q$), $T_{w_k}$ ($1 \le k \le m$), $T_x$ and $T_y$ to $u_i$, $v_j$, $w_k$, x,  y respectively (see Fig. 1). Moreover, let $S_n^{p,q,m}$ be the graph obtained from three internally disjointed paths $P_p, P_q$ and $P_m$ by identifying one common vertex x (or y) and center of the star $K_{1, n-2-p-q-m}$. In particular, if $p=q=1$ and $m=0$, then we denote $S_n^{1, 1, 0}$ by $B_2^{\sharp }(n)$. In addition, let $P_n^{p,q,m}$ be the graph obtained from three internally disjointed paths $P_p, P_q, P_m$ and attached an $(n-1-p-q-m)$-vertex path rooted at some vertex of $V(P_p)\cup V(P_q)\cup V(P_m)$ (see Fig. 3). In particular, if the bicyclic graph obtained from three internally disjoint paths $P_p=xu_1y, P_q=xv_1y, P_m=xy$ and attached an $(n-3)$-vertex path rooted at $v_1$, then we denote the graph by $B_2^{*}(n)$. In other words, $B_2^{*}(n)$ is the graph obtained by identifying a vertex with degree 2 in $K_4-e$ and an end vertex of an $(n-3)$-vertex path, where $K_4-e$ is a graph obtained by deleting one edge from complete graph $K_4$ (see Fig. 3).

Fig. 1

Illustration for graphs in ${\mathcal {B}}_1(n)$ and ${\mathcal {B}}_2(n)$

Fig. 2

$P^{p, q}_n$ and $S^{p, q}_n$

Fig. 3

$P_n^{p, q, m}$ and $S_n^{p, q, m}$

Next, we will present several important results which are useful in our proofs.

Theorem 2.1

[29] Let T be an n-vertex tree for $n\ge 3$. Then

$$\begin{aligned} 2n-2\le \varphi (T)\le (n-1)^2, \end{aligned}$$

(1)

The left equality holds if and only if T is $S_n$, and the right equality holds if and only if T is $P_n$.

Theorem 2.2

[30] Let G be any n-vertex unicyclic graph. Then

$$\begin{aligned} \min \left\{ \left\lfloor \frac{n}{2}\right\rfloor \left( n-\left\lfloor \frac{n}{2}\right\rfloor \right) , 2n+1\right\} \le \varphi (G)\le n^2-7. \end{aligned}$$

(2)

Theorem 2.3

[18] Let G be a connected graph and $x, y\in V(G)$. If there exists a cut vertex z such that x and y are not in a same component of $G-z$, then

$$\begin{aligned} H_{G}(x, y)=H_{G}(x, z)+H_{G}(z, y). \end{aligned}$$

(3)

Moreover, if there exists a unique path $P=xv_1\ldots v_{k-1}y$ in G, then

$$\begin{aligned} H_G(x, y)=H_G(x, v_1)+H_G(v_1, v_2)+ \cdots +H_G(v_{k-1}, y). \end{aligned}$$

(4)

Theorem 2.4

[4] Let G be a simple connected graph on n vertices and $x, y\in V(G)$. If there exists a unique path $P=v_0v_1\ldots v_k$ with $v_0=x$ and $v_k=y$, and $m_i$ is the number of edges of subgraph $G_i$, where $G_i$ is the component of $G-\{v_0v_1, v_1v_2, \ldots , v_{k-1}v_k\}$ containing $v_i$ for $i=0, \ldots , k$ (see Fig. 4), then

$$\begin{aligned} H_G(x, y)=k^2+2\sum _{i=0}^{k-1}m_i(k-i). \end{aligned}$$

(5)

Fig. 4

The components of $G-\{v_0v_1, v_1v_2, \ldots , v_{k-1}v_k\}$

Theorem 2.5

[24] Let $G_1$ and $G_2$ be decomposition of G through x and y with $V(G_1)\cap V(G_2)=\{x, y\}$ and $E(G_1)\cap E(G_2)=\emptyset$. Then

$$\begin{aligned} H_G(x, y)=\frac{R^2(x, y)}{R^1(x, y)+R^2(x, y)}H_{G_1}(x, y)+\frac{R^1(x, y)}{R^1(x, y)+R^2(x, y)}H_{G_2}(x, y), \end{aligned}$$

(6)

where $R^1(x, y)$ (resp. $R^2(x, y)$) is the effective resistance between x and y computed in graph $G_1$ (resp. $G_2$).

Lemma 2.6

[3] Let C be a cycle of length g. Then for any $x, y\in V(C)$, we have

$$\begin{aligned} H_C(x, y)=dist(x, y)(g-dist(x, y)). \end{aligned}$$

(7)

Theorem 2.7

[26] Let d(z) be the degree of vertex $z\in V(G)$ and e(G) be the edge number of G. Then

$$\begin{aligned} H_G(x, y)=\frac{1}{2}\sum _{z\in V(G)}d(z)(R_G(x, y)+R_G(y, z)-R_G(x, z)), \end{aligned}$$

(8)

and

$$\begin{aligned} H_G(x, y)+H_G(y, x)=2e(G)R_G(x, y). \end{aligned}$$

(9)

Lemma 2.8

[3] Let x be a vertex in graph G. Then the first return time is

$$\begin{aligned} H_{G}^{+}(x, x)=\frac{2e(G)}{d(x)}, \end{aligned}$$

(10)

where e(G) is the edge number of graph G.

Lemma 2.9

Let G be a simple connected graph. If there exist two vertices $x, y\in V(G)$ such that $\varphi (G)=H_G(x, y)$, then x and y are not cut vertices.

Proof

Suppose that y is a cut vertex. By (3) of Theorem 2.3, there exists a vertex $z\in N (y)$ such that $H_G(x, z)=H_G(x, y)+H_G(y, z)> H_G(x, y)$. Therefore, $H_G(x, y)$ can not be maximum which leads to a contradiction. Similarly, we can prove that x is not a cut vertex. $\square$

Lemma 2.10

Let x and y be the vertices of graph G and w be a vertex in N[y] such that $\max _{v\in N(y)} H_G(v, y)=H_G(w, y)$ and $d_{N[y]}(w)=t+1$, where $d_{N[y]}(w)$ denotes the degree of vertex w in N[y]. Let N be the vertex set of N[y] and G/N be the quotient graph obtained from G by contracting N to a single vertex (also denoted N) and identifying any resulting multiple edges.

• 1. If $N(y)\cap N(w)=\emptyset$, then $H_G(x, y)\le H_{G/N}(x, N)+ 1+2(e(G)-e(N[y]));$

• 2. If $N(y)\cap N(w)\ne \emptyset$, then $H_G(x, y)\le H_{G/N}(x, N)+ \frac{4e(G)-2e(N[y])-d(y)+t+1}{t+2},$

where e(G) (resp. e(N[y])) denotes the edge number of G (resp. N[y]).

Proof

First of all, if $u\in N$, then we give definitions of H(x, N), $H^{\prime }(w, N)$, p(x, u), p(w, w) and p(w, u).

• H(x, N): hitting time for a random walk from x to first hit N.

• $H^{\prime }(w, N)$: hitting time for a random walk from vertex w to first hit N, given that no edge inside N is used (i.e., the walk starts out by leaving N).

• p(x, u): probability that the random walk starting from vertex x to u before any other vertex of N, given that no edge inside N is used.

• p(w, w): probability that the random walk starting from vertex w to w before any other vertex of N, given that no edge inside N is used.

• p(w, u): probability that the random walk starting from vertex w to u before any other vertex of N, given that no edge inside N is used.

By above definitions, we can get

$$\begin{aligned} H(x, y)=H(x, N)+\sum _{u\in N(y)}p(x, u)H(u, y). \end{aligned}$$

(11)

Suppose that w sends k edges out of N[y]. Let E(N[y]) be the edge set of all edges in N[y] and $G-E(N[y])$ be the graph removed all the edges inside N[y] from G. Let $G^{\prime }$ be the component of $G-E(N[y])$ containing vertex w.

• (1) If $N(y)\cap N(w)=\emptyset$, then

  $$\begin{aligned} H_G(w, y) = \frac{1}{k+1}+\frac{k}{k+1}\left( H^{\prime }_{G^{\prime }}(w, N)+\sum _{u\in N(y)}p(w, u)H_G(u, y)\right) . \end{aligned}$$

  Since $H^{\prime }_{G^{\prime }}(w, N)+\max _{v\in N}H_G(v, y)\le H_{G^{\prime }}^{+}(w, w)+H_G(w, y)$ and $\sum _{u\in N(y)}p(w, u)\le 1$, by Lemma 2.8,

  $$\begin{aligned} H_{G^{\prime }}^{+}(w, w)=\,\,\frac{2e(G^{\prime })}{k}\le \frac{2\left( e(G)-e(N[y])\right) }{k}, \end{aligned}$$

  we have

  $$\begin{aligned} H_G(w, y)\le & {} \frac{1}{k+1}+\frac{k}{k+1}\left( H^{\prime }_{G^{\prime }}(w, N)+\sum _{u\in N(y)}p(w, u)H_G(w, y)\right) \\\le & {} \frac{1}{k+1}+\frac{k}{k+1}\left( H_{G^{\prime }}^{+}(w, w)+H_G(w, y)\right) \\=\,\, & {} \frac{1}{k+1}(1+kH_{G^{\prime }}^{+}(w, w)+kH_G(w, y))\\=\,\, & {} \frac{1}{k+1}\left( 1+2(e(G)-e(N[y]))+kH_G(w, y)\right) . \end{aligned}$$

  Thus,

  $$\begin{aligned} H_G(w, y)\le 1+2(e(G)-e(N[y])). \end{aligned}$$

  Further, $H_G(x, N)\le H_{G/N}(x, N)$, since that if multiple edges were kept when collapsing N[y] to a single vertex, the two expected hitting times would be the same. Removing duplicated edges can only make the collapsed N harder to hit. Therefore, by Eq. (11) and $\sum _{u\in N(y)}p(x, u)\le 1$, we have

  $$\begin{aligned} H_G(x, y)\le & {} H_G(x, N)+\sum _{u\in N(y)}p(x, u)H(w, y)\\\le & {} H_{G/N}(x, N)+H_G(w, y) \\\le & {} H_{G/N}(x, N)+1+2(e(G)-e(N[y])). \end{aligned}$$

• (2) If $N(y)=\{w, u_1, \ldots , u_t, v_1, \ldots , v_s\}$ and $N(w)\cap N(y)=\{ u_1, \ldots , u_t\}\ne \emptyset$, then

  $$\begin{aligned} H_G(w, y)=\,\, & {} \frac{1}{k+t+1}+\frac{1}{k+t+1}\left( \sum _{i=1}^t(1+H_G(u_i, y))\right) \\&\quad + \frac{k}{k+t+1}\left( H^{\prime }_{G^{\prime }}(w, N)+\sum _{v\in N(y)}p(w, v)H_G(v, y)\right) . \end{aligned}$$

Since $H_G^{+}(y, y)=\frac{2e(G)}{d(y)}$ and

$$\begin{aligned} H_G^{+}(y, y)= \,\,& {} 1+\frac{1}{d(y)}\sum _{u\in N(y)}H_G(u, y) \\=\,\, & {} 1+ \frac{1}{d(y)}H_G(w, y)+\frac{1}{d(y)}\sum _{i=1}^tH_G(u_i, y) +\frac{1}{d(y)}\sum _{j=1}^sH_G(v_j, y),\\ \end{aligned}$$

we have

$$\begin{aligned} \sum _{i=1}^t(1+H_G(u_i, y))=\,\, & {} 2e(G)-d(y)-\sum _{j=1}^sH_G(v_j, y)-H_G(w, y)+t \\\le & {} 2e(G)-d(y)-H_G(w, y)+t. \end{aligned}$$

Moreover, $H^{\prime }_{G^{\prime }}(w, N)+\max _{v\in N}H_G(v, y)\le H_{G^{\prime }}^{+}(w, w)+H_G(w, y)$, by Lemma 2.8,

$$\begin{aligned} H_{G^{\prime }}^{+}(w, w)=\frac{2e(G^{\prime })}{k}\le \frac{2\left( e(G)-e(N[y])\right) }{k}, \end{aligned}$$

we have

$$\begin{aligned} H_G(w, y)\le & {} \frac{1}{k+t+1}+\frac{1}{k+t+1}\left( \sum _{i=1}^t(1+H_G(u_i, y))\right) \\&\quad +\frac{k}{k+t+1}(H_{G^{\prime }}^{+}(w, w)+H_G(w, y))\\\le & {} \frac{1}{k+t+1}(1+2e(G)-d(y)-H_G(w, y)+t+kH_{G^{\prime }}^{+}(w, w)+kH_G(w, y))\\=\,\, & {} \frac{1}{k+t+1}\left( 4e(G)-2e(N[y])-d(y)+t+1+(k-1)H_G(w, y)\right) . \end{aligned}$$

Therefore,

$$\begin{aligned} H_G(w, y)\le \frac{4e(G)-2e(N[y])-d(y)+t+1}{t+2}. \end{aligned}$$

Since $H_G(x, y)\le H_{G/N}(x, N)+H_G(w, y)$, we have

$$\begin{aligned} H_G(x, y)\le H_{G/N}(x, N)+\frac{4e(G)-2e(N[y])-d(y)+t+1}{t+2}. \end{aligned}$$

$\square$

3 The Extremal Hitting Times on Bicyclic Graphs in ${\mathcal {B}}_1(n)$

Fig. 5

$B_1^*(n)$ and $B_1^{\sharp }(n)$

In this section, we will prove that the graph $B_1^*(n)$ is the n-maximal graph and $B_1^{\sharp }(n)$ (see Fig.  5) is the n-minimal graph among ${\mathcal {B}}_1(n)$.

Theorem 3.1

Let $G\in {\mathcal {B}}_1(n)$ and $f(n)=n^2+2n-27$. Then

$$\begin{aligned} \varphi (G)\le f(n). \end{aligned}$$

Moreover, equality holds if and only if $G=B_1^*(n)$ and $\varphi (B_1^*(n))=H_{B_1^*(n)}(x, y)$ is the hitting time from the vertex x in cycle with degree 2 to the pendant vertex y with $dist(x, y)=n-3$.

Fig. 6

$G_5^1$

Fig. 7

$G_6^1$, $G_6^2$, $G_6^3$, $G_6^4$

Proof

Let $\phi _1(n)=\max \{\varphi (G): G\in {\mathcal {B}}_1(n)\}$. We need to prove that $\phi _1(n)=f(n)$, and if G is any graph in ${\mathcal {B}}_1(n)$ with $\varphi (G)=f(n)$, then $G=B_1^*(n)$ and $H_{B_1^*(n)}(x,y)=\varphi (G)$, where x is a vertex in cycle with degree 2 and y is the pendant vertex such that $dist(x, y)=n-3$. We use the induction on n to prove it.

If $n=5$, then ${\mathcal {B}}_1(5)$ consists of only one graph $G_5^1$ which is the 5-vertex bicyclic graph obtained from two triangles sharing one common vertex (see Fig. 6). By simple computations, $\phi _1(5)=\varphi (G_5^1)=H_{G_5^1}(v_1, v_5)=8=f(5)$ and $dist(v_1, v_5)=2$.

If $n=6$, then ${\mathcal {B}}_1(6)$ consists of four graphs $G_6^1, G_6^2, G_6^3, G_6^4$ (see Fig. 7). By simple computations, we see that $\varphi (G_6^1)=H_{G_6^1}(v_1, v_6)=21$, $\varphi (G_6^2)=H_{G_6^2}(v_1, v_6)=15$, $\varphi (G_6^3)=H_{G_6^3}(v_1, v_6)=12$, $\varphi (G_6^4)=H_{G_6^4}(v_1, v_6)=\frac{49}{3}$. Hence, $\phi _1(6)=\max \{\varphi (G_6^1), \ldots , \varphi (G_6^4)\}=21=f(6)$. Thus, $G_6^1$ is the only 6-maximal graph in ${\mathcal {B}}_1(6)$ with $dist_{G_6^1}(v_1,v_6)=6-3=3$. Hence, $\phi _1(n)=f(n)$ for $n=5,6$. Moreover, when $n=5,6$, if G is any graph in ${\mathcal {B}}_1(n)$ with $\varphi (G)=f(n)$, then $G=B_1^*(n)$ and $H_{B_1^*(n)}(x,y)=\varphi (G)$, where x is a vertex in cycle with degree 2 and y is the pendant vertex such that $dist(x, y)=n-3$.

We assume that the assertion holds for $n-1$. In other words, $\phi _1(n-1)=f(n-1)$. Further, if G is any graph in ${\mathcal {B}}_1(n-1)$ with $\varphi (G)=f(n-1)$, then $G=B_1^*(n-1)$ and $H_{B_1^*(n-1)}(x,y)=\varphi (G)$, where x is a vertex in cycle with degree 2 and y is the pendant vertex such that $dist(x, y)=(n-1)-3$. Next, we will prove that the assertion holds for n. Without loss of generality, we assume that G is an n-maximal graph in ${\mathcal {B}}_1(n)$, i.e., $\varphi (G)=\phi _1(n).$

Then by the definition of $\varphi (G)$, there exist two vertices x and y in G such that $H_G(x, y)=\varphi (G)=\phi _1(n)$. By Lemma 2.9, y is not a cut vertex of G. Now we consider the following two cases.

Case 1. y is a vertex in cycle of G with $d(y)=2$. Then there exists a vertex w in N[y] such that $\max _{v\in N(y)}H_G(v, y)=H_G(w, y)$ and $d_{N[y]}(w)=t+1$. Furthermore, we consider the following two subcases.

Subcase 1.1. $t=0$. Then $e(N[y])=2$. By Lemma 2.10, $N(y)\cap N(w)=\emptyset$, $H_G(x, y)\le H_{G/N}(x, N)+2n-1.$ Moreover, G/N can be an $(n-2)$-vertex unicyclic graph or $G/N\in {\mathcal {B}}_1(n-2)$.

If G/N is an $(n-2)$-vertex unicyclic graph, by Theorem 2.2, then $H_{G/N}(x, N)\le (n-2)^2-7$ and $H_G(x, y)\le n^2-4n-3+2n-1=n^2-2n-4 < f(n)$.

If $G/N\in {\mathcal {B}}_1(n-2)$, then $H_{G/N}(x, N)\le (n-2)^2+2(n-2)-27$ and $H_G(x, y)\le n^2-2n-27+2n-1=n^2-28<f(n)$.

Subcase 1.2. $t=1$. Then $e(N[y])=3$. By Lemma 2.10, $N(y)\cap N(w)\ne \emptyset$, $H_G(x, y)\le H_{G/N}(x, N)+\frac{4n-2}{3}.$ Moreover, G/N is an $(n-2)$-vertex unicyclic graph, by Theorem 2.2, $H_{G/N}(x, N)\le (n-2)^2-7$ and $H_G(x, y)\le n^2-4n-3+\frac{4n-2}{3}= \frac{3n^2-8n-11}{3}< f(n)$ for $n\ge 6$.

Therefore, if y is a vertex in cycle of G with $d(y)=2$, then $\phi_1 (n)=\varphi (G)<f(n)$.

Case 2. y is a pendant vertex of G, there exists a unique neighbor v of y in G. Then v must be a cut vertex in G and $G^{-}{:}{=}G-y$ is an $(n-1)$-vertex connected bicyclic graph. By Theorem 2.3, we have $H_G(x, y)=H_G(x, v)+H_G(v, y)=H_{G^{-}}(x, v)+H_G(v, y)$. Moreover, by Theorem 2.4, $H_G(v, y)=2n+1$.

On the one hand, by the induction hypothesis for $G^-$, $H_{G^{-}}(x, v) \le \phi _1(n-1)=f(n-1)=\varphi (B_1^*(n-1))$. Hence,

$$\begin{aligned} \phi _1(n)=\varphi (G)=H_G(x,y)=H_{G^-}(x,v)+H_G(v,y)\le f(n-1)+2n+1=f(n). \end{aligned}$$

On the other hand, let x be a vertex of degree 2 in cycle and y be the pendant vertex in $B_1^*(n)$ such that $dist(x, y)=n-3$. We denote a unique neighbor of y by v. By the induction hypothesis, we have

$$\begin{aligned} \phi _1(n)\ge & {} \varphi (B_1^*(n))\ge H_{B_1^*(n)}(x,y)\\=\,\, & {} H_{B_1^*(n)}(x,v)+H_{B_1^*(n)}(v,y)\\=\,\, & {} H_{B_1^*(n-1)}(x,v)+2n+1\\=\,\, & {} f(n-1)+2n+1=f(n). \end{aligned}$$

Hence, $\phi _1(n)=f(n)$. Furthermore, if G is any n-vertex graph in ${\mathcal {B}}_1(n)$ with $\varphi (G)=\phi _1(n)=f(n)$. Then there exist two vertices x and y such that $H_G(x,y)=\varphi (G)=f(n)$. Then y must be a pendant vertex. We denote a unique neighbor of y by v. Then $G-y$ is an $(n-1)$-vertex bicyclic graph in ${\mathcal {B}}_1(n-1)$. By the induction hypothesis,

$$\begin{aligned} f(n)=\,\, & {} H_G(x,y)=H_G(x,v)+H_G(v,y)\\=\,\, & {} H_{G-y}(x,v)+2n+1\\\le & {} \varphi (G-y)+2n+1\\\le & {} f(n-1)+2n+1=f(n), \end{aligned}$$

which implies that $\varphi (G-y)= H_{G-y}(x,v)=f(n-1)$. By the induction hypothesis, $G-y$ must be $B_1^*(n-1)$ and v is the pendant vertex in $B_1^*(n-1)$. Thus, $G=B_1^*(n)$ and $f(n)=\varphi (B_1^*(n))=H_{B_1^*(n)}(x,y)$, where x is a vertex in cycle and y is a pendant vertex with $dist(x,y)=n-3$. Therefore, the assertion holds for all n. $\square$

Next, we will consider the n-minimal graph among ${\mathcal {B}}_1(n)$.

Theorem 3.2

Let $G{:}{=}B(T_{u_1}, \ldots , T_{u_p}, T_{w_0}, \ldots , T_{w_{m-1}}, T_{v_1}, \ldots , T_{v_q})$ be a connected bicyclic graph with at least one pendant vertex in ${\mathcal {B}}_1(n)$. Then $\varphi (G)\ge 2n+3$ with equality holds if and only if $G=B_1^{\sharp }(n)$.

Proof

Let v be the pendant vertex in G. Then there exists a vertex $u_i$ (resp. $v_j$ or $w_k$) such that $v\in V(T_{u_i})$ (resp. $v\in V(T_{v_j})$ or $v\in V(T_{w_k})$), where $1\le i\le p.$ (resp. $1\le j\le q,\, 0\le k\le m-1$). If $v\in V(T_{u_i})$, by Theorem 2.4 and $dist(u_i, v)\ge 1$, then $H_{G}(u_i, v)\ge 1+2n$, with equality holds if and only if $dist(u_i, v)=1$. Moreover, by Theorem 2.5 and Lemma 2.6, there exists a vertex $u_j$ in cycle $C_p$ such that $H_{G}(u_j, u_i)\ge 2$, with equality holding for $C_p=C_3$ and $T_{u_j}=u_j$, $T_{u_t}=u_t$ for $u_j, u_t\in V(C_3)$. Hence,

$$\begin{aligned} \varphi (G)\ge H_{G}(u_{j}, v)=H_{G}(u_{j}, u_i)+H_{G}(u_i, v)\ge 2+1+2n=2n+3. \end{aligned}$$

Similarly, if $v\in V(T_{v_j})$, by a similar argument, $\varphi (G)\ge H_{G}(v_{i}, v)\ge 2n+3$. If $v\in V(T_{w_k})$ and $w_k\ne u_1, v_1$, by Theorem 2.4 and $dist(w_k, v)\ge 2$, then $\varphi (G)> H_{G}(w_{k}, v)> 2n+3.$ Moreover, $\varphi (B_1^{\sharp }(n))=2n+3$. Therefore, $\varphi (G)\ge 2n+3$, with equality holds if and only if $G= B_1^{\sharp }(n)$. So the assertion holds. $\square$

4 The Extremal Hitting Times on Bicyclic Graphs in ${\mathcal {B}}_2(n)$

Fig. 8

$B_2^*(n)$ and $B_2^{\sharp }(n)$

In this section, we will prove that the graph $B_2^*(n)$ is the n-maximal graph and $B_2^{\sharp }(n)$ is the n-minimal graph among ${\mathcal {B}}_2(n)$ (see Fig. 8).

Theorem 4.1

Let $G\in {\mathcal {B}}_2(n)$ and $g(n)=n^2+2n-19$. Then

$$\begin{aligned} \varphi (G)\le g(n). \end{aligned}$$

Moreover, equality holds if and only if $G=B_2^*(n)$ and $\varphi (B_2^*(n))=H_{B_2^*(n)}(x,y)$ is the hitting time from the vertex x in cycle with degree 2 to the pendant vertex y with $dist(x,y)=n-2$.

Proof

Let $\phi _2(n)=\max \{\varphi (G): G \in {\mathcal {B}}_2(n)\}$. We need to prove that $\phi _2(n)=g(n)=n^2+2n-19$, and prove that for any graph G with $\varphi (G)=g(n)$, then $G=B_2^*(n)$ and $g(n)=H_{B_2^*(n)}(x,y)$ with $dist (x,y)=n-2$, where x is vertex of degree 2 in cycle and y is the pendant vertex. We use the induction on n to prove the assertion. If $n=5$, then ${\mathcal {B}}_2(5){:}{=}\{G_5^1, G_5^2, G_5^3, G_5^4\}$ (see Fig. 9). By a simple computation, $\varphi (G_5^1)=H_{G_5^1}(v_1, v_5)=16$, $\varphi (G_5^2)=H_{G_5^2}(v_1, v_5)=13.5$, $\varphi (G_5^3)=H_{G_5^3}(v_4, v_1)=\frac{79}{11}$, $\varphi (G_5^4)=H_{G_5^4}(v_1, v_5)=6$. Hence, $\phi _2(5)= \max \{\varphi (G): G \in {\mathcal {B}}_2(5)\}= g(5)=\varphi (G_5^1)= H_{G_5^1}(v_1,v_5)$ with $dist(v_1, v_5)=5-2$. So the assertion holds for $n=5$.

Fig. 9

$G_5^1, G_5^2, G_5^3, G_5^4$

Suppose that the assertion holds for $n-1$, i.e., $\phi _2(n-1)=g(n-1)$. Moreover, if G is any $(n-1)$-vertex bicyclic graph G with $\varphi (G)=\phi _2(n-1)$, then $G=B_2^*(n-1)$ and there exists a vertex x with degree 2 and a pendant vertex y in $B_2^*(n-1)$ such that $H_{B_2^*(n-1)}(x,y)=\varphi (B_2^*(n-1))=\phi _2(n-1)=g(n-1)$ and $dist(x,y)=n-3$.

Let G be any n-vertex bicyclic graph in ${\mathcal {B}}_2(n)$ such that $\varphi (G)=\phi _2(n)$. Next, we will prove that $\phi _2(n)= g(n)$ with equality holds if and only if $G=B_2^*(n)$.

In addition, by the definition of $\varphi (G)$, there exist two vertices x and y in G such that $H_G(x, y)= \varphi (G)=\phi _2(n)$. By Lemma 2.9, y is not a cut vertex. Let w be a vertex in N[y] such that $\max _{v\in N(y)}H_G(v, y)=H_G(w, y)$ and $d_{N[y]}(w)=t+1$. We consider the following three cases.

Case 1. y is a vertex in cycle with $d(y)=2$. Then we need to consider the following two subcases.

Subcase 1.1. $t=0$. By Lemma 2.10, we have $N(y)\cap N(w)=\emptyset$, then $e(N[y])=2$ and $H_G(x, y)\le H_{G/N}(x, N)+2n-1$. In addition, G/N has four cases, $G/N\in {\mathcal {B}}_2(n-2)$, $G/N\in {\mathcal {B}}_1(n-2)$, G/N is an $(n-2)$-vertex unicyclic graph, or G/N is an $(n-2)$-vertex tree.

If $G/N\in {\mathcal {B}}_2(n-2)$, then $H_G(x, y)\le (n-2)^2+2(n-2)-19+2n-1=n^2-20<g(n).$

If $G/N\in {\mathcal {B}}_1(n-2)$, by Theorem 3.1, then $H_G(x, y)\le (n-2)^2+2(n-2)-27+2n-1=n^2-28<g(n).$

If G/N is an $(n-2)$-vertex unicyclic graph, by Theorem 2.2 and $n\ge 5$, then $H_G(x, y)\le (n-2)^2-7+2n-1<g(n).$

If G/N is an $(n-2)$-vertex tree, then by Theorem 2.1 and $n\ge 5$, we have $H_G(x, y)\le (n-3)^2+2n-1<g(n).$

Subcase 1.2. $t=1$. By Lemma 2.10, we have $N(y)\cap N(w)\ne \emptyset$. Then $e(N[y])=3$ and $H_G(x, y)\le H_{G/N}(x, N)+\frac{4n-2}{3}$. In addition, G/N is either an $(n-2)$-vertex tree or an $(n-2)$-vertex unicyclic graph.

If G/N is an $(n-2)$-vertex tree, then $H_G(x, y)\le (n-3)^2+\frac{4n-2}{3}<g(n).$

If G/N is an $(n-2)$-vertex unicyclic graph, then $H_G(x, y)\le (n-2)^2-7+\frac{4n-2}{3}<g(n).$

Case 2. y is a vertex in cycle with $d(y)=3$. Then we need to consider the following three subcases.

Subcase 2.1. $t=0$. By Lemma 2.10, we have $N(y)\cap N(w)=\emptyset$. Then $e(N[y])=3$ (resp. $e(N[y])=4$) and $H_G(x, y)\le H_{G/N}(x, N)+2n-3$ (resp. $H_G(x, y)\le H_{G/N}(x, N)+2n-5$).

On the one hand, if $e(N[y])=3$, then G/N has four cases, $G/N\in {\mathcal {B}}_2(n-3)$, $G/N\in {\mathcal {B}}_1(n-3)$, G/N is an $(n-3)$-vertex unicyclic graph, or G/N is an $(n-3)$-vertex tree.

If $G/N\in {\mathcal {B}}_2(n-3)$, then $H_G(x, y)\le (n-3)^2+2(n-3)-19+2n-3<g(n).$

If $G/N\in {\mathcal {B}}_1(n-3)$, then by Theorem 3.1, $H_G(x, y)\le (n-3)^2+2(n-3)-27+2n-3<g(n).$

If G/N is an $(n-3)$-vertex unicyclic graph, then by Theorem 2.2, $H_G(x, y)\le (n-3)^2-7+2n-3<g(n).$

If G/N is an $(n-3)$-vertex tree, then $H_G(x, y)\le (n-4)^2+2n-3<g(n).$

On the other hand, if $e(N[y])=4$, then G/N is either an $(n-3)$-vertex tree or an $(n-3)$-vertex unicyclic graph.

If G/N is an $(n-3)$-vertex tree, then $H_G(x, y)\le (n-4)^2+2n-5<g(n).$

If G/N is an $(n-3)$-vertex unicyclic graph, then $H_G(x, y)\le (n-3)^2-7+2n-5<g(n).$

Subcase 2.2. $t=1$. By Lemma 2.10, we have $N(y)\cap N(w)\ne \emptyset$. Then $e(N[y])=4$ (resp. $e(N[y])=5$) and $H_G(x, y)\le H_{G/N}(x, N)+\frac{4n-5}{3}$ (resp. $H_G(x, y)\le H_{G/N}(x, N)+\frac{4n-7}{3}$).

On the one hand, if $e(N[y])=4$, then G/N is either an $(n-3)$-vertex tree or an $(n-3)$-vertex unicyclic graph.

If G/N is an $(n-3)$-vertex tree, then $H_G(x, y)\le (n-4)^2+\frac{4n-5}{3}<g(n).$

If G/N is an $(n-3)$-vertex unicyclic graph, then $H_G(x, y)\le (n-3)^2-7+\frac{4n-5}{3}<g(n).$

On the other hand, if $e(N[y])=5$, then G/N is an $(n-3)$-vertex tree. Thus, $H_G(x, y)\le (n-4)^2+\frac{4n-7}{3}<g(n).$

Subcase 2.3. $t=2$. By Lemma 2.10, we have $N(y)\cap N(w)\ne \emptyset$. Then $e(N[y])=5$ and $H_G(x, y)\le H_{G/N}(x, N)+\frac{2n-3}{2}$. Moreover, G/N is an $(n-3)$-vertex tree, by Theorem 2.1, $H_G(x, y)\le (n-4)^2+\frac{2n-3}{2}<g(n).$

Case 3. y is a pendant vertex of G. Then there exists a unique neighbor v of y in G. Let $G^{-}=G-y$. Then v must be a cut vertex. By Theorem 2.3, we have $H_G(x, y)=H_G(x, v)+H_G(v, y)=H_{G^{-}}(x, v)+H_G(v, y)$. By Theorem 2.4, $H_G(v, y)=2n+1$.

On the one hand, by the induction hypothesis, we have

$$\begin{aligned} H_{G^{-}}(x, v) \le \varphi (G^-)\le \phi _2(n-1)=g(n-1). \end{aligned}$$

Hence,

$$\begin{aligned} \phi _2(n)=\varphi (G)\le \phi _2(n-1)+2n+1=g(n-1)+2n+1=g(n). \end{aligned}$$

On the other hand, let $u_1$, $u_2$ be two vertices in $B_2^*(n)$ with $d(u_1)=2$, $d(u_2)=1$ and $dist(u_1,u_2)=n-2$. We denote the unique neighbor of $u_2$ by w. By the definition of $\phi _2(n)$ and the induction hypothesis, we have

$$\begin{aligned} \phi _2(n)\ge & {} \varphi (B_2^*(n))\ge H_{B_2^*(n)}(u_1,u_2)\\=\,\, & {} H_{B_2^*(n)}(u_1,w)+H_{B_2^*(n)}(w,u_2)\\=\,\, & {} H_{B_2^*(n-1)}(u_1,w)+2n+1\\=\,\, & {} g(n-1)+2n+1=g(n). \end{aligned}$$

Hence, $\phi _2(n)=g(n)$. Moreover, $\phi _2(n)=\varphi (B_2^*(n))=H_{B_2^*(n)}(u_1,u_2)=g(n)$. For any n-maximal graph G with $\varphi (G)=\phi _2(n)=g(n)$, there exist two vertices x and y such that $H_G(x,y)=\varphi (G)=g(n)$. By above proof, y must be a pendant vertex in G. In addition, let v be a unique neighbor of y. Then $g(n)=H_G(x,y)\le \varphi (G-y)+2n+1\le g(n-1)+2n+1=g(n)$, which implies that $\varphi (G-y)=g(n-1)$. By the induction hypothesis, we have $G-y=B_2^*(n-1)$. Therefore, $G=B_2^*(n)$. We finish our proof. $\square$

Next, we will consider the n-minimal graph among ${\mathcal {B}}_2(n)$.

Lemma 4.2

Let $G\in {\mathcal {B}}_2(n)$ without pendant vertices, i.e., G consists of three internally disjoint paths $P_p{:}{=}xu_1u_2\ldots u_py,P_q{:}{=}xv_1\ldots v_{q}y$ and $P_{m}{:}{=} xw_1\ldots w_{m}y$. If $G^{\prime }$ is obtained from G by adding a pendant edge e to one root vertex, then $H_{G^{\prime }}(x, y)\ge H_G(x, y)$ for any two vertices $x, y \in V(G)$.

Proof

By Ohm’s law, we have known that $R_G(x, y)=R_{G^{\prime }}(x, y)$ for $x, y\in V(G)$ and the new added pendant edge has no effect on the effective resistance of any two vertices in graph G . Suppose that the new added vertex is $u_0$ and v is the unique neighbour of $u_0$. By Lemma 2.7 and triangle inequality $R_{G^{\prime }}(x, y)+R_{G^{\prime }}(y, z)-R_{G^{\prime }}(x, z)\ge 0$, we have

$$\begin{aligned} H_{G^{\prime }}(x, y)=\,\, & {} \frac{1}{2}\sum _{z\in V(G^{\prime })}d_{G^{\prime }}(z)(R_{G^{\prime }}(x, y)+R_{G^{\prime }}(y, z)-R_{G^{\prime }}(x, z))\\=\,\, & {} \frac{1}{2}\sum _{z\in V(G)}d_G(z)(R_{G^{\prime }}(x, y)+R_{G^{\prime }}(y, z)-R_{G^{\prime }}(x, z)) \\&+ \frac{1}{2}(R_{G^{\prime }}(x, y)+R_{G^{\prime }}(y, v)-R_{G^{\prime }}(x, v)) \\&+ \frac{1}{2}\sum _{z=u_0}d(z)(R_{G^{\prime }}(x, y)+R_{G^{\prime }}(y, z)-R_{G^{\prime }}(x, z)) \\=\,\, & {} H_G(x, y)+ \frac{1}{2}(R_{G^{\prime }}(x, y)+R_{G^{\prime }}(y, v)-R_{G^{\prime }}(x, v))\\&+\frac{1}{2}(R_{G^{\prime }}(x, y)+R_{G^{\prime }}(y, u_0)-R_{G^{\prime }}(x, u_0))\\\ge & {} H_G(x, y). \end{aligned}$$

$\square$

Lemma 4.3

Let $G\in {\mathcal {B}}_2(n)$ without pendant vertices, i.e., G consists of three internally disjoint paths $P_p{:}{=}xu_1u_2\ldots u_py,P_q{:}{=}xv_1\cdots v_{q}y$ and $P_{m}{:}{=} xw_1\ldots w_{m}y$. Let u and v be two vertices in $V(P_p)$ with $dist_{P_p}(u, v)=d_1$, $dist_{P_p}(x, u)=d_2$ and $dist_{P_p}(v, y)=d_3$ (see Fig. 10). Then

$$\begin{aligned} H_G(u, v)=\,\, & {} \frac{R_2}{d_1+R_2}d_1^2+\frac{d_1}{d_1+R_2}\left( d_2^2+qm+q+m+1\right) \\&+\frac{d_1}{d_1+R_2}\left( \frac{2d_2(q+1)(m+1)}{q+m+2} +d_3^2+2d_3(d_2+q+m+2)\right) , \end{aligned}$$

where $R_2=d_2+d_3+\frac{(q+1)(m+1)}{q+m+2}$.

Fig. 10

A decomposition of G

Proof

We can decompose graph G into $G_1$ and $G_2$ through vertices u and v, where $G_1$ is a uv-path and $G_2$ is a unicyclic graph (see Fig. 10). Let $R_1$ be the effective resistance between u and v in $G_1$ and $R_1=d_1$. Let $R_2$ be the effective resistance between u and v in $G_2$ and $R_2=d_2+d_3+\frac{(q+1)(m+1)}{q+m+2}$. By Theorems 2.4 and 2.5, we have

$$\begin{aligned} H_G(u, v)=\,\, & {} \frac{R_2}{R_1+R_2}H_{G_1}(u, v)+\frac{R_1}{R_1+R_2}H_{G_2}(u, v) \\=\,\, & {} \frac{R_2}{d_1+R_2}d_1^2+\frac{d_1}{d_1+R_2}(d_2^2+qm+q+m+1)\\&+\frac{d_1}{d_1+R_2}\left( \frac{2d_2(q+1)(m+1)}{q+m+2} +d_3^2+2d_3(d_2+q+m+2)\right) . \end{aligned}$$

$\square$

By Lemma 4.3, we can get the following Corollary.

Corollary 4.4

Let $G\in {\mathcal {B}}_2(n)$ without pendant vertices, i.e., G consists of three internally disjoint paths $P_p{:}{=}xu_1u_2\ldots u_py,P_q{:}{=}xv_1\ldots v_{q}y$ and $P_{m}{:}{=} xw_1\ldots w_{m}y$. Then

$$\begin{aligned} H_G(x, y)=\frac{(n+1)(p+1)(q+1)(m+1)}{(p+1)(q+1)+(p+1)(m+1)+(q+1)(m+1)}. \end{aligned}$$

Lemma 4.5

Let $G\in {\mathcal {B}}_2(n)$ without pendant vertices, i.e., G consists of three internally disjoint paths $P_p{:}{=}xu_1u_2\ldots u_py,P_q{:}{=}xv_1\ldots v_{q}y$ and $P_{m}{:}{=} xw_1\ldots w_{m}y$. Let $u\in V(P_p)$ with $dist_{P_p}(u, x)=d_1$ and $v\in V(P_q)$ with $dist_{P_q}(v, x)=d_2$. Then

$$\begin{aligned} R_G(u, v)=\,\, & {} d_1+d_2-\frac{d_1^2}{p+m+2}\\&\quad -\frac{\left[ d_2(p+m+2) +d_1(m+1)\right] ^2}{(p+m+2)(pq+pm+qm+2p+2q+2m+3)}. \end{aligned}$$

Proof

By the method of calculating the effective resistance for bridge circuit (see Fig. 11), we can get $R_G(u, v).$ More details about bridge circuit can be referred to [2].

Fig. 11

Bridge circuit and G

Let $R_1=d_1$, $R_2=d_2$, $R_3=m+1$, $R_4=p+1-d_1$ and $R_5=q+1-d_2$. Then

$$\begin{aligned} R_G(u, v)=\,\, & {} d_1+d_2-\frac{d_1^2}{p+m+2}\\&\quad -\frac{[d_2(p+m+2) +d_1(m+1)]^2}{(p+m+2)(pq+pm+qm+2p+2q+2m+3)}. \end{aligned}$$

$\square$

Theorem 4.6

Let $G\in {\mathcal {B}}_2(n)$ with at least one pendant vertex. Then $\varphi (G)\ge 2n+3.5$ with equality holds if and only if $G=B_2^{\sharp }(n)$.

Proof

$G\in {\mathcal {B}}_2(n)$ has at least one pendant vertex, i.e., G can be obtained from three internally disjointed paths $P_p, P_q, P_m$ with common end vertices x, y by attaching the trees rooted at each vertex in $P_p, P_q$ and $P_m$. Without loss of generality, we assume that v is a pendant vertex of G, i.e., there exists one vertex z for $z\in V(P_p)\cup V(P_q) \cup V(P_m)$ such that $v\in V(T_z)$ and $|V(T_{z})|\ge 2$. By Theorem 2.4 and $dist(z, v)\ge 1$, we have $H_G(z, v)\ge 1+2n$, with equality holds if and only if $dist(z, v)=1$. By Lemma 4.2, 4.3 and Corollary 4.4, if $p+q+m\ge 3$, then there must exist a vertex $u^{\prime }$ in cycle such that $H_G(u^{\prime }, z)> 2.5$. Since z is a cut vertex, by Theorem 2.3, we have $\varphi (G)\ge H_G(u^{\prime }, v)= H_G(u^{\prime }, z)+ H_G(z, v)> 2n+3.5.$ If $p+q+m=2$, i.e., $p=q=1$ and $m=0$, then there must exist a vertex $u^{\prime }$ in cycle such that $H_G(u^{\prime }, z)\ge 2.5$, the equality holds if and only if $u^{\prime }, z\in V(K_4-e)$ and $u^{\prime }, z$ are common end vertices of three internally disjoint paths in $K_4-e$, $T_{u^{\prime }}=u^{\prime }$, $T_{u_1}=u_1$ and $T_{v_1}=v_1$ for $u_1, v_1\in V(K_4-e)$. Since z is a cut vertex, by Theorem 2.3, we have $\varphi (G)\ge H_G(u^{\prime }, v)= H_G(u^{\prime }, z)+ H_G(z, v)\ge 2n+3.5.$ Therefore, by Theorems 2.4, 2.5 and Lemma 4.2, we have $\varphi (B_2^{\sharp }(n))=2n+3.5$ and $\varphi (G)\ge 2n+3.5$, with equality holds if and only if $G=B_2^{\sharp }(n)$. $\square$

5 Proof of Theorem 1.2

In this section, we are ready to present the proof of Theorem 1.2.

Fig. 12

Illustration for graph in ${\mathcal {B}}_1(n)$ without pendant trees

Proof of Theorem 1.2

For the upper bound, by Theorems 3.1 and 4.1, then

$$\begin{aligned} \varphi (G)\le n^2+2n-19. \end{aligned}$$

For the lower bound, we consider the following two cases.

Case 1. $G\in {\mathcal {B}}_1(n)$, then G has two cycles of length p and q with no common edges and $p\ge q$. Furthermore, we consider the following three subcases.

Subcase 1.1. G has at least one pendant vertex. Then by Theorem 3.2, $\varphi (G)\ge 2n+3$ with equality holding if and only if $G=B_1^{\sharp }(n)$.

Subcase 1.2. G has no pendant vertices and two cycles in G has no common vertex. Then $n+1>p+q$ and $|V(T_{u_i})|=1$ for $i=1, \ldots , p$, $|V(T_{w_j})|=1$ for $j=0, \ldots , m-1$, $|V(T_{v_r})|=1$ for $r=1, \ldots q$ (see Fig. 12). Moreover, there exist two vertices $u,v\in V(G)$ such that $\varphi (G)=H_G(u, v)$. Then by Lemma 2.9, either u, v are vertices in different cycles, or u, v are vertices in the same cycle.

Let

$$\begin{aligned} M= \left\lfloor \frac{p}{2}\right\rfloor \left\lceil \frac{p}{2}\right\rceil +\left\lfloor \frac{q}{2}\right\rfloor \left\lceil \frac{q}{2}\right\rceil \frac{2(n+1)-q}{q}+(n+1-p-q)(n+1+p-q). \end{aligned}$$

By $n+1-p-q\ge 1$, $p\ge q$ and $p\ge 3,$ we have $M>2n+3$ .

If $u\in V(C_p)$, $v\in V(C_q)$, $dist(u, u_1)=g_1$, and $dist(v_1, v)=g_2$, by Theorems 2.3, 2.4 and 2.5, then

$$\begin{aligned} H_G(u, v)=\,\, & {} H_G(u, u_1)+H_G(u_1, v_1)+H_G(v_1, v) \\=\,\, & {} g_1(p-g_1)+(n+1-p-q)(n+1+p-q)\\&+g_2(q-g_2)+\frac{2g_2(q-g_2)(n+1-q)}{q} \\\le & {} \left\lfloor \frac{p}{2}\right\rfloor \left\lceil \frac{p}{2}\right\rceil +\left\lfloor \frac{q}{2}\right\rfloor \left\lceil \frac{q}{2}\right\rceil \frac{2(n+1)-q}{q}\\&\quad +(n+1-p-q)(n+1+p-q), \end{aligned}$$

with equality holds if and only if $g_1=\left\lfloor \frac{p}{2}\right\rfloor$ and $g_2=\left\lfloor \frac{q}{2}\right\rfloor$.

If $u\in V(C_q)$ and $v\in V(C_p)$, then by similar arguments,

$$\begin{aligned} H_G(u, v)\le & {} \left\lfloor \frac{q}{2}\right\rfloor \left\lceil \frac{q}{2}\right\rceil +\left\lfloor \frac{p}{2}\right\rfloor \left\lceil \frac{p}{2}\right\rceil \frac{2(n+1)-p}{p}\\&\quad +(n+1-p-q)(n+1+q-p)\le M. \end{aligned}$$

If $u, v\in V(C_p)$, $dist(u, v)=g_1$, and $dist(u_1, v)=t_1$, by Theorems 2.3, 2.4 and 2.5, then $H_G(u, v)=g_1(p-g_1)+\frac{2g_1(n+1-p)t_1}{p}.$ Since $t_1\le p-g_1$, we have

$$\begin{aligned} H_G(u, v)\le & {} g_1(p-g_1)+\frac{2g_1(p-g_1)(n+1-p)}{p} \\\le & {} g_1(p-g_1)\frac{2n+2-p}{p}\\\le & {} \left\lfloor \frac{p}{2}\right\rfloor \left\lceil \frac{p}{2}\right\rceil \frac{2n+2-p}{p}\le M. \end{aligned}$$

If $u, v\in V(C_q)$, The by similar arguments, $H_G(u, v)\le \left\lfloor \frac{q}{2}\right\rfloor \left\lceil \frac{q}{2}\right\rceil \frac{2n+2-q}{q}\le M.$

Hence, $\varphi (G)=M>2n+3.$

Subcase 1.3. G has no pendant vertices and two cycles $C_p$ and $C_q$ in G have one common vertex. Then $p+q=n+1$. Let

$$\begin{aligned} M_0= \max \left\{ \left\lfloor \frac{p}{2}\right\rfloor \left\lceil \frac{p}{2}\right\rceil +\left\lfloor \frac{q}{2}\right\rfloor \left\lceil \frac{q}{2}\right\rceil \frac{2(n+1)-q}{q},\ \ \left\lfloor \frac{q}{2}\right\rfloor \left\lceil \frac{q}{2}\right\rceil +\left\lfloor \frac{p}{2}\right\rfloor \left\lceil \frac{p}{2}\right\rceil \frac{2(n+1)-p}{p}\right\} . \end{aligned}$$

From Subcase 1.2, we can get $\varphi (G)=M_0>2n+3$ for $n\ge 8$.

Case 2. $G\in {\mathcal {B}}_2(n)$. We consider the following two subcases.

Subcase 2.1. G has at least one pendant vertex. By Theorem 4.6, we have $\varphi (G)\ge 2n+3.5.$

Subcase 2.2. G has no pendant vertices. Then $p+q+m=n-2$.

By Lemma 4.5 and $n\ge 12$, $p\ge q\ge m$, we have $p\ge 4$ and there exists $u\in V(P_p)$ and $v\in V(P_q)$ such that $R_G(u, v)>2.2$. Furthermore, by (9) in Theorem 2.7, we have $H_G(u, v)+H_G(v, u)=2(n+1)R_{G}(u, v)>4.4(n+1)$, which implies that $2\varphi (G)\ge H_G(u, v)+H_G(v, u)>4.4(n+1)$. So $\varphi (G)\ge 2.2n+2.2>2n+3.5$ for $n\ge 12$. We complete the proof of Theorem 1.2. $\square$

Remark

If $n\le 11$, then the left inequality in Theorem 1.2 does not hold. In fact, by a simple calculation and argument, $\varphi (G)\ge 5, 16, \frac{69}{8}, \frac{80}{7}, 13, 18, 22, 24$ for $n=4, 5, 6, 7, 8, 9, 10, 11$ respectively; while $n\ge 5$, the right inequality holds in Theorem 1.2. It is natural to ask the analogous question for n-vertex tricyclic graphs (n-vertex connected graphs with $n+2$ edges). We guess that there exists N such that the maximal and minimal extremal graphs in the set of all n-vertex tricyclic graphs with $n\ge N$ are the following two graphs (see Fig. 13).

Fig. 13

The extremal graphs of n-vertex tricyclic graphs

Generally, we guess the extremal graphs in Question 1.1, that is, n-maximal graph is $G^*$ and n-minimal graph is $G^{\sharp }$ (see Fig. 14). From Fig. 14, we can see that the extremal graph $G^*$ is a graph obtained by identifying one vertex in $G_0$ and an end vertex of a path on remaining vertices, $G^{\sharp }$ is a graph obtained by identifying one vertex in $G_1$ and center of a star, where $G_0$ and $G_1$ are subgraphs of $G^*$ and $G^{\sharp }$ respectively and $G_0$ is a clique or close to a clique probably. Moreover, if the edge number m of G is equal to $n+k$ with $k\ge 0$, then $G_1$ is a graph consists of $k+1$ triangles sharing one common vertex. If $\phi (n)=\varphi (G)=H_G(x, y)$, then x is a vertex in $V(G_0)$ and y is a pendant vertex. If $\psi (n)=\varphi (G)=H_G(x, y)$, then x is a vertex with degree 2 in $V(G_1)$ and y is a pendant vertex.

Fig. 14

The extremal graphs $G^*$ and $G^{\sharp }$ in ${\mathcal {G}}_{n, m}$