双圈图中Hitting Time的极值问题

Extremal Problems on the Hitting Time of Bicyclic Graphs

摘要: 设H_G(x,y)是图G上的随机游走中，从顶点x到顶点y的步数的期望值。本文主要研究一类双圈图G中φ(G)的极值问题，其中φ(G)=max{H_G(x,y):x,y∈V(G)}。利用有效电阻，刻画出了在这类双圈图中，φ(G)达到极值时，相应的极图以及两点在图中的位置。

Abstract: Let H_G(x,y) be the expected steps from vertex x to vertex y on random walk on graph G. In this paper, we will consider the extremal values of φ(G) in bicyclic graphs G, where φ(G)=max{H_G(x,y):x,y∈V(G)}. By using effective resistance, we characterize the corresponding extremal graph and the position of two vertices in the graph when φ(G) reaches the extremum.

1. 引言

本文只考虑简单连通图 $G=\left(V\left(G\right),E\left(G\right)\right)$，其中 $V\left(G\right)$ 是G的顶点集， $E\left(G\right)$ 是G的边集。对两个点 $x,y\in V\left(G\right)$，x和y之间的距离用 $d_G\left(u,v\right)$ 表示。对于任意点 $x\in V\left(G\right)$，与x相关联的边的数目叫做x在G的度，记作 $d_G\left(x\right)$。

在 [1] 中，Klein和Randić提出了一个图上的新的距离函数——有效电阻。把图G中的每条边看作电阻值为1的电阻，点x和y之间的电阻值，叫做点x和y之间的有效电阻，记为 $r\left(x,y\right)$。显然，当图G是树时， $r\left(x,y\right)=d\left(x,y\right)$。我们把 $R^w\left(x\right)={\displaystyle {\sum }_{y\in V\left(G\right)}d\left(y\right)r\left(x,y\right)}$ 叫做点x的weighted resistance centrality [2]。

给定一个图G，通常将G上的随机游走定义为马尔可夫链。图G上的随机游走中，顶点x跳到邻点的概率为 $\text{1}/d\left(x\right)$，那么G中从顶点x到顶点y的hitting time [3] $H_G\left(x,y\right)$ 是随机游走中步数的期望值。图G的hitting time定义为

$\phi \left(G\right)=\max \left\{H_G\left(x,y\right):x,y\in V\left(G\right)\right\}$。

Zhang和Li [4] 得到了树中 $\phi \left(G\right)$ 的上界和下界，并且表明星图达到下界以及路径达到上界。此外，Zhu和Zhang [5] [6] 得到了单圈图中 $\phi \left(G\right)$ 的上界和下界，并且确定了极图。本文将继续研究有关问题。我们将刻画双圈图中 $\phi \left(G\right)$ 的上界和下界所对应的极值图。

2. 预备知识

双圈图G是满足 $\left|E\left(G\right)\right|=\left|V\left(G\right)\right|+\text{1}$ 的简单连通图。本文只考虑基本型为 $\infty$ -型 $B\left(p,l,q\right)$ 的双圈图。设 $B\left(p,l,q\right)$ 是一个双圈图，其两个圆 $C_p$ 和 $C_q$ 之间有一条长为l的路径。当 $l\ge 2$ 时，路径 $P_l$ 和圆 $C_p$ 和 $C_q$ 的交点分别为u和v。当l = 1时，我们仍然使用u = v来表示圆 $C_p$ 和 $C_q$ 的交点。

图簇 ${\mathcal{B}}_n\left(p,l,q\right)$ 被定义为阶数为n的图的集合，这些图是由在 $B\left(p,l,q\right)$ 顶点处悬挂树得到的。在本文中，我们使用 $\left\{v_1,v_2,\cdots ,v_{p+q+l-2}\right\}$ 来表示 $B\left(p,l,q\right)$ 的顶点，每个挂在顶点 $v_i$ 的树用 $T_i$ 表示，其点的个数用 $n_i$ 表示，图G可用 $B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)$ 表示，其中 $n_1+\cdots +n_{p+q+l-2}=n$。请注意，我们将使用 $T_u\left(T_v\right)$ 表示悬挂在 $u\left(v\right)$ 点的树。

我们现在列出以下重要引理。

引理2.1. [2] 设T是n个点的树，对任意的两个点 $x,y\in V\left(T\right)$，有 $1\le H_T\left(x,y\right)\le {\left(n-1\right)}^2$。

引理2.2. [7] 设G是边数为m的简单连通图。那么，对于 $x,y\in V\left(G\right)$，有

$H\left(x,y\right)=mr\left(x,y\right)+\frac{1}{2}{R}^w\left(y\right)-R^w\left(x\right)$。

引理2.3. [8] 设G是一个n个点的简单连通图，点 $x,y\in V\left(G\right)$。如果存在唯一的一条路径 $P=v_0{v}_1\cdots v_k$，其中 $v_0=x$ 和 $v_k=y$，且对于 $i=0,\cdots ,k$， $m_i$ 是 $G-\left\{v_{i-1}{v}_i,v_{i+1}\right\}$ 包含 $v_i$ 的部分的边数， $v_{-1}{v}_0=\varnothing$ 和 $v_k{v}_{k+1}=\varnothing$，那么有 $H\left(x,y\right)=k^2+2{\displaystyle {\sum }_{i=0}^{k-1}{m}_i\left(k-i\right)}$。

引理2.4. [1] 设z是连通图G的割点，x，y是G-z的不同部分中的两个顶点。那么有 $H\left(x,y\right)=H\left(x,z\right)+H\left(z,y\right)$。而且，如果G中存在一条唯一的路径 $P=x{v}_1\cdots v_{k-1}$，那么有 $H\left(x,y\right)=H\left(x,v_1\right)+H\left(v_1,v_2\right)+\cdots +H\left(v_{k-1},y\right)$。

引理2.5. [5] 设G是圈长为g且点数为n的单圈图，那么 $\phi \left(G\right)\le \lfloor \frac{q}{2}\rfloor \left(q-\lfloor \frac{q}{2}\rfloor \right)+n^2-q^2$。

引理2.6. [9] 设 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 和 $x\in V\left(T_k\right)$。那么 $R^w\left(x\right)=2R\left(x\right)+2d\left(x,v_k\right)+r\left(x,u\right)+r\left(x,v\right)-\left(n-p-q-l+2\right)$。

令 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，对任意的 $x\in V\left(T_i\right)$， $y\in V\left(T_j\right)$，由引理2.2和2.6，显然有

$\begin{array}{c}H\left(x,y\right)=\left(n+1\right)r\left(x,y\right)+R\left(y\right)-R\left(x\right)+d\left(y,v_j\right)-d\left(x,v_i\right)\\ +\frac{1}{2}\left(r\left(y,u\right)+r\left(y,v\right)-\left(r\left(x,u\right)+r\left(x,v\right)\right)\right).\end{array}$ (1)

3. $\phi \left(G\right)$ 的最大值

引理3.1. 令 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$。如果 $V\left(G\right)$ 中存在两个顶点x，y，使得 $\phi \left(G\right)=H\left(x,y\right)$，则x和y要么是 $V\left(G\right)$ 中的悬挂点，要么是 $V\left(B\left(p,q,l\right)\right)$ 中度为2的点。

证明：假设 $V\left(G\right)$ 中的点y既不是 $V\left(G\right)$ 中的悬挂点，也不是 $V\left(B\left(p,q,l\right)\right)$ 中度为2的点，那么它一定是一个割点。由引理2.4，则存在点 $z~y$ 使得 $H\left(x,z\right)=H\left(x,y\right)+H\left(y,z\right)>H\left(x,y\right)$。因此， $H\left(x,y\right)$ 不是最大的，这与条件相矛盾。因此，y要么是 $V\left(G\right)$ 中的悬挂点，要么是 $V\left(B\left(p,q,l\right)\right)$ 中度为2的点。类似地，我们可以证明x要么是 $V\left(G\right)$ 中的悬挂点，要么是 $V\left(B\left(p,q,l\right)\right)$ 中度为2的点。

引理3.2. 设 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 和 $G^{\prime }=B\left({T^{\prime }}_1,{T^{\prime }}_2,\cdots ,{T^{\prime }}_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，如果 $T_i={T^{\prime }}_i$ 和 $T_j={T^{\prime }}_j$，其中 $i\ne j$， $x\in V\left(T_i\right)$， $y\in V\left(T_j\right)$，且 $\left|T_r\right|=\left|{T^{\prime }}_r\right|$， $r=1,2,\cdots ,p+q+l-2$，那么 $H\left(x,y\right)=H_{G^{\prime }}\left(x,y\right)$。

证明：在不失一般性的前提下，假设 $2<i<j<p+q+l-2$。由引理2.4，我们有 $H\left(x,y\right)=H\left(x,v_i\right)+H\left(v_i,v_j\right)+H_{G^{\prime }}\left(x,v_i\right)$ 和 $H_{G^{\prime }}\left(x,y\right)=H_{G^{\prime }}\left(x,v_i\right)+H_{G^{\prime }}\left(v_i,v_j\right)+H_{G^{\prime }}\left(v_j,y\right)$。显然，由引理2.3，有 $H\left(x,v_i\right)=H_{G^{\prime }}\left(x,v_i\right)$ 和 $H_{G^{\prime }}\left(x,v_i\right)=H_{G^{\prime }}\left(v_j,y\right)$。那么由式子(1)，我们有 $H\left(v_i,v_j\right)-H_{G^{\prime }}\left(v_i,v_j\right)=R\left(v_j\right)-R_{G^{\prime }}\left(v_j\right)+R_{G^{\prime }}\left(v_i\right)-R\left(v_i\right)=0$。

这就得出了我们要的结论。

引理3.3. 设 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$。如果 $V\left(T_p\right)$ 中存在一个悬挂点w，其中 $G^{\prime }$ 是从G中删除w的关联边并添加一条连接点w和 $T_i$ 中的一个顶点的边而得到的图，那么对于任意的两个点 $x\in V\left(T_i\right)$ 和 $y\in V\left(T_j\right)$ 且 $i,j\ne p$，有 $H_{G^{\prime }}\left(x,y\right)\ge H\left(x,y\right)$。

证明：假设在 $G^{\prime }$ 中 $w~z_1$。由式子(1)，我们有

$\begin{array}{l}H\left(x,y\right)-H_{G^{\prime }}\left(x,y\right)=R\left(y\right)-R\left(x\right)-\left(R_{G^{\prime }}\left(y\right)-R_{G^{\prime }}\left(x\right)\right)\\ =r\left(v_j,v_p\right)-r\left(v_j,v_i\right)-r\left(v_i,v_p\right)+r\left(x,z_1\right)-r\left(x,v_i\right)-r\left(v_i,z_1\right)\le 0\end{array}$

这就得出了我们要的结论。

引理3.4. 设 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，存在两个点 $x\in V\left(T_i\right)$ 和 $y\in V\left(T_j\right)$， $i\ne j$，且有 $\phi \left(G\right)=H\left(x,y\right)$。设 $G_1=B\left(T_1^1,T_2^1,\cdots ,T_{p+q+l-2}^1\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，且 $T_i^1=P_i$， $\left|V\left(T_i\right)\right|=\left|V\left(P_i\right)\right|$，对于 $r\ne i$，有 $T_r^1=T_r$。设 ${G^{\prime }}_1=B\left({T^{\prime }}_1,{T^{\prime }}_2,\cdots ,{T^{\prime }}_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，且 ${T^{\prime }}_j=P_j$， $\left|V\left(T_j\right)\right|=\left|V\left(P_j\right)\right|$，对于 $r\ne j$，有 ${T^{\prime }}_r=T_r$。假设点x和y分别在 $P_i$ 和 $P_j$ 上，那么它们要不是悬挂点，要不 $V\left(B_{p,q,l}\right)$ 中度为2的点，且有 $H_{G_1}\left(x,y\right)\ge H\left(x,y\right)$ 和 $H_{{G^{\prime }}_1}\left(x,y\right)\ge H\left(x,y\right)$。

证明：由引理3.1，我们知道x和y要不是 $V\left(G\right)$ 中的悬挂点，要不是 $V\left(B_{p,q,l}\right)$ 中度为2的点。我们考虑下面这三种情况。

情况1. x和y都是 $V\left(B_{p,q,l}\right)$ 中度为2的点。

由引理3.2，我们有 $H_{G_1}\left(x,y\right)=H\left(x,y\right)$ 和 $H_{{G^{\prime }}_1}\left(x,y\right)=H\left(x,y\right)$。

情况2. 假设 $\left|V\left(T_i\right)\right|\ge 2$， $x\in V\left(T_i\right)$ 是一个悬挂点和 $y\in V\left(T_j\right)$。

此外，我们有 $x\in V\left(P_i\right)$ 是 $V\left(G_1\right)$ 中的一个悬挂点。由引理2.4，我们有 $H\left(x,y\right)=H\left(x,v_i\right)+H\left(v_i,v_j\right)+H\left(v_j,y\right)$ 和 $H_{G_1}\left(x,y\right)=H_{G_1}\left(x,v_i\right)+H_{G_1}\left(v_i,v_j\right)+H_{G_1}\left(v_j,y\right)$。根据hitting time的定义和引理2.1，我们有 $H\left(x,v_i\right)=H_{T_1}\left(x,v_i\right)\le {\left(n_i-1\right)}^2=H_{G_1}\left(x,v_i\right)$。此外，由引理3.2，我们有 $H\left(v_i,v_j\right)=H_{G_1}\left(v_i,v_j\right)$。此外，由定理2.3，很容易看出， $H\left(v_j,y\right)=H_{G_1}\left(v_j,y\right)$。因此， $H_{G_1}\left(x,y\right)\ge H\left(x,y\right)$。

情况3. 假设 $\left|V\left(T_j\right)\right|\ge 2$， $y\in V\left(T_j\right)$ 是一个悬挂点和 $x\in V\left(T_i\right)$。

此外，我们有 $y\in V\left(P_j\right)$ 是 $V\left({G^{\prime }}_1\right)$ 中的一个悬挂点。由引理2.4，我们有 $H_{{G^{\prime }}_1}\left(x,y\right)=H_{{G^{\prime }}_1}\left(x,v_i\right)+H_{{G^{\prime }}_1}\left(v_i,v_j\right)+H_{{G^{\prime }}_1}\left(v_j,y\right)$。显然， $H_{{G^{\prime }}_1}\left(x,v_i\right)=H_{T_1}\left(x,v_i\right)=H\left(x,v_i\right)$ 和 $H_{{G^{\prime }}_1}\left(v_i,v_j\right)=H\left(v_i,v_j\right)$。因此，我们只需要比较 $H_{{G^{\prime }}_1}\left(v_j,y\right)$ 和 $H\left(v_j,y\right)$。设P是从点 $v_j$ 到点y的唯一路径，且 $P=v_0{v}_1\cdots v_k$， $v_0=v_j$ 和 $v_k=y$。对于 $i=0,\cdots ,k$，设 $G_i^{*}$ 是G中删除 $v_{i-1}{v}_i$ 和 $v_i{v}_{i+1}$ 且包含点 $v_i$ 的子图，其中 $v_{-1}{v}_0=\varnothing$ 和 $v_k{v}_{k+1}=\varnothing$。设 $m_i^{*}$ 是 $G_i^{*}$ 的边数，那么 $m_0^{*}+m_1^{*}+\cdots +m_{k-1}^{*}+k-1=n$。由引理2.3，我们有 $H\left(v_j,y\right)=k^2+2{\displaystyle {\sum }_{i=0}^{k-1}{m}_i^{*}\left(k-i\right)}$ 和 $H_{{G^{\prime }}_1}\left(v_j,y\right)={\left(n_j-1\right)}^2+2\left(n-n_j+2\right)\left(n_j-1\right)=-{\left(n_j-1\right)}^2+2\left(n+1\right)\left(n_j-1\right)$。因此，

$\begin{array}{l}{H}_{{G^{\prime }}_1}\left(v_j,y\right)-H\left(v_j,y\right)\\ =-{\left(n_j-1\right)}^2+2\left(n+1\right)\left(n_j-1\right)-\left(k^2+2{\displaystyle {\sum }_{i=0}^{k-1}{m}_i^{*}\left(k-i\right)}\right)\\ =\left(n_j-k-1\right)\left(2n-k-n_j+3\right)+2{\displaystyle {\sum }_{i=0}^{k-1}{m}_i^{*}i}\ge 0,\end{array}$

其中 $1\le k\le n_j-1$。如果 $\left|V\left(T_i\right)\right|=1$，那么x是 $V\left(B\left(p,q,l\right)\right)$ 中度为2的一个点。因此 $H_{{G^{\prime }}_1}\left(x,y\right)\ge H\left(x,y\right)$。

设 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，那么对于 $i\ne j$，G中存在两个顶点 $x\in V\left(T_i\right)$ 和 $y\in V\left(T_j\right)$，使得 $\phi \left(G\right)=H\left(x,y\right)$。

设 $G_2=B\left(T_1^2,T_2^2,\cdots ,T_{p+q+l-2}^2\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 中有 $T_i^2=P_i$ 和 $T_j^2=P_j$，且有 $\left|V\left(P_i\right)\right|=\left|V\left(T_i\right)\right|$ 和 $\left|V\left(P_j\right)\right|=\left|V\left(T_j\right)\right|$，对于 $r\ne i,j$，有 $T_r^2=T_r$。

设 $G_3=B\left(T_1^3,T_2^3,\cdots ,T_{p+q+l-2}^3\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 中有 $T_i^3=P_i$，且对于 $i=1,\cdots ,p+q+l-2$，有 $\left|V\left(P_i\right)\right|=\left|V\left(T_i\right)\right|$。

设 $G_4=B\left(T_1^4,T_2^4,\cdots ,T_{p+q+l-2}^4\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 中有 $T_i^4=P_i$， $T_j^4=P_j$，且对于 $r\ne i,j$，有 $\left|V\left(T_r^4\right)\right|=1$。

设 $G_5=B\left(T_1^5,T_2^5,\cdots ,T_{p+q+l-2}^5\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 中有一棵唯一的树， $T_i^5=P_i$ 或者 $T_j^5=P_j$，并且对于 $r\ne i$ 或者 $r\ne j$，有 $\left|V\left(T_r^5\right)\right|=1$。

推论3.5. $H\left(x,y\right)\le \phi \left(G\right)\le H_{G_2}\left(x,y\right)=H_{G_3}\left(x,y\right)\le \phi \left(G_3\right)\le H_{G_4}\left(x,y\right)\le \phi \left(G_4\right)$。

证明：由引理3.3，3.4，结论显然成立。

引理3.6. 设x和y是 $G_4$ 中的两个顶点，且有 $H_{G_4}\left(x,y\right)=\phi \left(G_4\right)$， $x\in V\left(T_k\right)$， $y\in V\left(T_z\right)$。那么 $\phi \left(G_4\right)\le H_{G_5}\left(x,y\right)$。

证明：由引理3.1，x和y要么是悬挂点要么是圈上度为2的点。我们考虑以下四种情况。

情况1. x和y都是 $G_4$ 的圈上度为2的点。由式子(1)，我们有

$\begin{array}{c}{H}_{G_4}\left(x,y\right)=R_{B\left(p,q,l\right)}\left(y\right)-R_{B\left(p,q,l\right)}\left(x\right)+\left(n+1\right)r_{G_4}\left(x,y\right)\\ +\frac{1}{2}\left(r_{G_4}\left(y,u\right)+r_{G_4}\left(y,v\right)-r_{G_4}\left(x,u\right)-r_{G_4}\left(x,v\right)\right)\\ +\left(n_i-1\right)\left(r_{G_4}\left(y,v_i\right)-r_{G_4}\left(x,v_i\right)\right)+\left(n_j-1\right)\left(r_{G_4}\left(y,v_j\right)-r_{G_4}\left(x,v_j\right)\right).\end{array}$

当x和y都固定时，

$R_{B\left(p,q,l\right)}\left(y\right)-R_{B\left(p,q,l\right)}\left(x\right)+\left(n+1\right)r_{G_4}\left(x,y\right)+\frac{1}{2}\left(r_{G_4}\left(y,u\right)+r_{G_4}\left(y,v\right)-r_{G_4}\left(x,u\right)-r_{G_4}\left(x,v\right)\right)$

也是个定值。因为

$\begin{array}{l}\left(n_i+n_j-2\right)\max \left\{r_{G_4}\left(y,v_i\right)-r_{G_4}\left(x,v_i\right),r_{G_4}\left(y,v_j\right)-r_{G_4}\left(x,v_j\right)\right\}\\ \ge \left(n_i-1\right)\left(r_{G_4}\left(y,v_i\right)-r_{G_4}\left(x,v_i\right)\right)+\left(n_j-1\right)\left(r_{G_4}\left(y,v_j\right)-r_{G_4}\left(x,v_j\right)\right),\end{array}$

所以我们有 $\phi \left(G_4\right)\le H_{G_5}\left(x,y\right)$。

情况2. x是 $G_4$ 的悬挂点，记作 $x\in V\left(P_i^4\right)$，也就是i = k，和y是 $G_4$ 的圈上度为2的点。由式子(1)，我们有

$\begin{array}{c}{H}_{G_4}\left(x,y\right)=\left(n+1\right)r_{G_4}\left(v_k,y\right)+R_{B\left(p,q,l\right)}\left(y\right)-R_{B\left(p,q,l\right)}\left(v_k\right)\\ +\frac{1}{2}\left(r_{G_4}\left(y,u\right)+r_{G_4}\left(y,v\right)-r_{G_4}\left(v_k,u\right)-r_{G_4}\left(v_k,v\right)\right)\\ +\left(n_k-1\right)\left(r_{G_4}\left(v_k,y\right)+n_k-1\right)+\left(n_j-1\right)\left(r_{G_4}\left(v_j,y\right)-r_{G_4}\left(v_k,v_j\right)\right).\end{array}$

当x和y都固定时，

$\left(n+1\right)r_{G_4}\left(v_k,y\right)+R_{B\left(p,q,l\right)}\left(y\right)-R_{B\left(p,q,l\right)}\left(v_k\right)+\frac{1}{2}\left(r_{G_4}\left(y,u\right)+r_{G_4}\left(y,v\right)-r_{G_4}\left(v_k,u\right)-r_{G_4}\left(v_k,v\right)\right)$

也是个定值。但是

$\left(n_i+n_j-2\right)\left(r_{G_4}\left(v_i,y\right)+n_i+n_j-2\right)>\left(n_i-1\right)\left(r_{G_4}\left(y,v_i\right)-r_{G_4}\left(x,v_i\right)\right)+\left(n_j-1\right)\left(r_{G_4}\left(y,v_j\right)-r_{G_4}\left(x,v_j\right)\right)$，

这与G的选择所矛盾，所以 $\phi \left(G_4\right)\le H_{G_5}\left(x,y\right)$。

情况3. y是 $G_4$ 中的一个悬挂点，记作 $y\in V\left(P_j^4\right)$，也就是j = z，和x是 $G_4$ 的圈上度为2的点。由式子(1)，我们有

$\begin{array}{c}{H}_{G_4}\left(x,y\right)=\left(n+1\right)r_{G_4}\left(v_k,v_j\right)+\frac{1}{2}\left(r_{G_4}\left(v_j,u\right)+r_{G_4}\left(v_j,v\right)-r_{G_4}\left(x,u\right)-r_{G_4}\left(x,v\right)\right)\\ +R_{B\left(p,q,l\right)}\left(v_j\right)-R_{B\left(p,q,l\right)}\left(x\right)+\left(n_i-1\right)\left(r_{G_4}\left(v_i,v_j\right)-r_{G_4}\left(v_k,v_i\right)\right)\\ +\left(n_j-1\right)\left(2n-n_j+3-r_{G_4}\left(v_k,v_j\right)\right).\end{array}$

当x和y都固定时，

$\left(n+1\right)r_{G_4}\left(v_k,v_j\right)+\frac{1}{2}\left(r_{G_4}\left(v_j,u\right)+r_{G_4}\left(v_j,v\right)-r_{G_4}\left(x,u\right)-r_{G_4}\left(x,v\right)\right)+R_{B\left(p,q,l\right)}\left(v_j\right)-R_{B\left(p,q,l\right)}(\; x\; )$

也是个定值。但是

$\begin{array}{l}\left(n_i+n_j-2\right)\left(2n-n_i-n_j+4-r_{G_4}\left(v_k,v_j\right)\right)\\ >\left(n_j-1\right)\left(2n-n_j+3-r_{G_4}\left(v_k,v_j\right)\right)+\left(n_i-1\right)\left(r_{G_4}\left(v_i,v_j\right)-r_{G_4}\left(v_k,v_i\right)\right),\end{array}$

这与G的选择所矛盾，所以 $\phi \left(G_4\right)\le H_{G_5}\left(x,y\right)$。

情况4. $x\in V\left(P_i^4\right)$ 和 $y\in V\left(P_j^4\right)$ 都是 $G_4$ 的悬挂点，也就是i = k，j = z。由式子(1)，有

$\begin{array}{c}{H}_{G_4}\left(x,y\right)=\left(n+1\right)\left(n_i+n_j+r_{G_4}\left(v_i,v_j\right)-2\right)+R_{B\left(p,q,l\right)}\left(v_j\right)-R_{B\left(p,q,l\right)}\left(v_i\right)\\ +\frac{1}{2}\left(r_{G_4}\left(v_j,u\right)+r_{G_4}\left(v_j,v\right)-\left(r_{G_4}\left(v_i,u\right)+r_{G_4}\left(v_i,v\right)\right)\right)\\ +\left(n_j-n_i\right)\left(n-n_i-n_j+3-r_{G_4}\left(v_i,v_j\right)\right).\end{array}$

当x和y都固定时，

$\begin{array}{l}\left(n+1\right)\left(n_i+n_j+r_{G_4}\left(v_i,v_j\right)-2\right)+R_{B\left(p,q,l\right)}\left(v_j\right)-R_{B\left(p,q,l\right)}\left(v_i\right)\\ +\frac{1}{2}\left(r_{G_4}\left(v_j,u\right)+r_{G_4}\left(v_j,v\right)-\left(r_{G_4}\left(v_i,u\right)+r_{G_4}\left(v_i,v\right)\right)\right)\end{array}$

也是个定值。但是 $\left(n_i+n_j-2\right)\left(n-n_i-n_j+3-r_{G_4}\left(v_i,v_j\right)\right)>\left(n_j-n_i\right)\left(n-n_i-n_j+3-r_{G_4}\left(v_i,v_j\right)\right)$，这与G的选择所矛盾，所以 $\phi \left(G_4\right)\le H_{G_5}\left(x,y\right)$。所以结论成立。

又一次令 $B_{n,v_k}\left(p,l,q\right)$ 是通过在 $B\left(p,l,q\right)$ 的 $v_k$ 处连接 $P_{n-p-q-l+3}$ 的一个端点的图。设 $M=n^2-{\left(p+q+l-2\right)}^2$ 和

$k_1=\lfloor \frac{q}{2}\rfloor \left(q-\lfloor \frac{q}{2}\rfloor \right)+{\left(q+l-1\right)}^2-q^2+\frac{\left(2q+2l+p-2\right)\lfloor \frac{p}{2}\rfloor \lceil \frac{p}{2}\rceil }{p},$

$k_2=\lfloor \frac{p}{2}\rfloor \left(p-\lfloor \frac{p}{2}\rfloor \right)+{\left(p+l-1\right)}^2-p^2+\frac{\left(2p+2l+q-2\right)\lfloor \frac{q}{2}\rfloor \lceil \frac{q}{2}\rceil }{p},$

$k_3=\left(q+l-1\right)\left(\frac{3\left(\lfloor \frac{p}{2}\rfloor \lceil \frac{p}{2}\rceil -p\right)-1}{p}\right)+\frac{\left(q+l+p-1\right)\lfloor \frac{p}{2}\rfloor \lceil \frac{p}{2}\rceil }{p},$

$k_4=\left(p+l-1\right)\left(\frac{3\left(\lfloor \frac{q}{2}\rfloor \lceil \frac{q}{2}\rceil -q\right)-1}{p}\right)+\frac{\left(q+l+p-1\right)\lfloor \frac{q}{2}\rfloor \lceil \frac{q}{2}\rceil }{p}.$

定理3.7. $\phi \left(B_{n,v_k}\left(p,l,q\right)\right)\le \max \left\{k_1+M,k_2+M,k_3+M,k_4+M\right\}$。

证明：设x和y是 $B_{n,v_k}\left(p,l,q\right)$ 中的两个点并且 $x\in V\left(T_i\right)$， $y\in V\left(T_j\right)$，那么 $\phi \left(B_{n,v_k}\left(p,l,q\right)\right)=H_{B_{n,v_k}\left(p,l,q\right)}\left(x,y\right)$。由引理3.1，点x和y要么是悬挂点，要么是圈上度为2的点。由推论3.5，我们知道x或者y是悬挂点。如果x是一个悬挂点并且 $y=v_j$ 是 $B_{n,v_i}\left(p,l,q\right)$ 中的圈上度为2的点，那么假设 $y_1\in V\left(T_j\right)$ 是一个悬挂点且 $x_1=v_i$ 是 $B_{n,v_j}\left(p,l,q\right)$ 中的圈上度为2的点，就有

$\begin{array}{l}{H}_{B_{n,v_i}\left(p,l,q\right)}\left(x,y\right)-H_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)\left(x_1,y_1\right)\\ =R_{B\left(p,q,l\right)}\left(v_j\right)+\left(n_i-1\right)\left(r_{B\left(p,q,l\right)}\left(v_i,v_j\right)+1\right)+\underset{i=1}{\overset{n_i-2}{{\displaystyle \sum }}}i-\left(\underset{i=1}{\overset{n_i-2}{{\displaystyle \sum }}}i+\left(n_i-1\right)\left(n-n_i+1\right)+R_{B\left(p,q,l\right)}\left(v_j\right)\right)\\ -\left(\underset{i=1}{\overset{n_i-2}{{\displaystyle \sum }}}i+\left(n_i-1\right)\left(n-n_i+1\right)+R_{B\left(p,q,l\right)}\left(v_i\right)-R_{B\left(p,q,l\right)}\left(v_i\right)-\left(n_i-1\right)\left(r_{B\left(p,q,l\right)}\left(v_i,v_j\right)+1\right)-\underset{i=1}{\overset{n_i-2}{{\displaystyle \sum }}}i\right)-4\left(n_i-1\right)\\ =2\left(n_i-1\right)\left(r_{B\left(p,q,l\right)}\left(v_i,v_j\right)+n_i-n\right)-4\left(n_i-1\right)<0\end{array}$

所以，y是一个悬挂点且 $x=v_i$ 是 $B_{n,v_j}\left(p,l,q\right)$ 中的圈上度为2的点，那么 $\phi \left(B_{n,v_j}\left(p,l,q\right)\right)=H_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)$。假设 $x\in V\left(C_p\right)$ 和 $v_j\in V\left(P_l\right)$， $d\left(u,v_j\right)=l_1$， $0\le l_1\le l-1$，那么有

$\begin{array}{c}{H}_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)=l_1^2+\left(n+2+p-q-l\right)l_1+\frac{l^2-3l+2}{2}+\left(n+1\right)r_{B\left(p,q,l\right)}\left(x,u\right)\\ +\left(n_j-1\right)\left(n-\frac{n_j}{2}+3\right)+\frac{p^2-1}{6}+\frac{q^2-1}{6}+\left(q+1\right)\left(l-1\right)\text{.}\end{array}$

设 $f\left(l_1\right)=l_1^2+\left(n+2+p-q-l\right)l_1$。由二次函数的性质，我们知道 $f\left(l_1\right)$ 取到它的最大值当且仅当 $l_1=0$ 或者 $l_1=l-1$，这如同 $H_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)$。所以 $v_j$ 是 $B_{n,v_j}\left(p,l,q\right)$ 中的圈上度为2的点，且 $\phi \left(B_{n,v_j}\left(p,l,q\right)\right)=H_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)$。对点 $v_j$ 和x的具体位置，我们分以下几种情况讨论。

情况1. $V_j\in V\left(C_p\right)$ 和 $x\in V\left(C_q\right)$。

由引理2.5，有 $H_{U_{q+l-1,q}}\left(x,u\right)\le \lfloor \frac{q}{2}\rfloor \left(q-\lfloor \frac{q}{2}\rfloor \right)+{\left(q+l-1\right)}^2-q^2$。所以我们有

$\begin{array}{l}{H}_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)=\left\{H_{B_{n,v_j}\left(p,l,q\right)}\left(x,u\right)+H_{B_{n,v_j}\left(p,l,q\right)}\left(u,v_j\right)+H_{B_{n,v_j}\left(p,l,q\right)}\left(p,l,q\right)\right\}\left(v_j,y\right)\\ =\left\{H_{U_{q+l-1,q}}\left(x,u\right)+H_{B_{n,v_j}\left(p,l,q\right)}\left(u,v_j\right)+H_{B_{n,v_j}\left(p,l,q\right)}\left(p,l,q\right)\right\}\left(v_j,y\right)\\ \le \lfloor \frac{q}{2}\rfloor \left(q-\lfloor \frac{q}{2}\rfloor \right)+{\left(q+l-1\right)}^2-q^2+\left(n+q+l-n_j+1\right)r_{B\left(p,q,l\right)}\left(v_j,u\right)+{\left(n_j-1\right)}^2+2\left(n-n_j+1\right)\left(n_j-1\right)\\ \le \lfloor \frac{q}{2}\rfloor \left(q-\lfloor \frac{q}{2}\rfloor \right)+{\left(q+l-1\right)}^2-q^2+\frac{\left(2q+2l+p-2\right)\lfloor \frac{p}{2}\rfloor \lceil \frac{p}{2}\rceil }{p}+M\text{.}\end{array}$

情况2. $v_j\in V\left(C_q\right)$ 和 $x\in V\left(C_p\right)$。同情况1讨论类似，我们有

$H_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)\le \lfloor \frac{p}{2}\rfloor \left(p-\lfloor \frac{p}{2}\rfloor \right)+{\left(p+l-1\right)}^2-p^2+\frac{\left(2p+2l+q-2\right)\lfloor \frac{q}{2}\rfloor \lceil \frac{q}{2}\rceil }{p}+M.$

情况3. $v_j$ 和x都在 $C_p$ 上。那么

$\begin{array}{l}{H}_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)=H_{B_{n,v_j}\left(p,l,q\right)}\left(x,v_j\right)+H_{B_{n,v_j}\left(p,l,q\right)}\left(v_j,y\right)\\ =\left(n-n_j+2\right)r_{B\left(p,q,l\right)\left(x,v_j\right)}+\left(q+l-1\right)\left(r_{B\left(p,q,l\right)}\left(u,v_j\right)-r_{B\left(p,q,l\right)}\left(x,u\right)\right)+{\left(n_j-1\right)}^2+2\left(n-n_j+1\right)\left(n_j-1\right)\\ \le \frac{\left(p+q+l-1\right)\lfloor \frac{p}{2}\rfloor \lceil \frac{p}{2}\rceil }{p}+\left(q+l-1\right)\left(r_{B\left(p,q,l\right)}\left(u,v_j\right)-r_{B\left(p,q,l\right)}\left(x,u\right)\right)+M\text{.}\end{array}$

如果路径x-u-v_j的长度是 $\lfloor \frac{p}{2}\rfloor$ 和路径u-x-v_j的长度是 $p-p_1+2$，其中 $2\le p_1\le \lfloor \frac{p}{2}\rfloor -1$，那么

$\begin{array}{c}{r}_{B\left(p,q,l\right)}\left(u,v_j\right)-r_{B\left(p,q,l\right)}\left(x,u\right)=\frac{\left(p_1-1\right)\left(p-p_1+1\right)-\left(\lfloor \frac{p}{2}\rfloor -p_1\right)\left(\lceil \frac{p}{2}\rceil +p_1-2\right)}{p}\\ \le \frac{\left(p-\lfloor \frac{p}{2}\rfloor +\lceil \frac{p}{2}\rceil \right)\left(\lfloor \frac{p}{2}\rfloor -1\right)-\lfloor \frac{p}{2}\rfloor \left(2-\lceil \frac{p}{2}\rceil \right)-p-1}{p}\text{.}\end{array}$

如果路径x-u-v_j的长度是 $\lceil \frac{p}{2}\rceil$ 和路径u-x-v_j的长度是 $p-p_1+2$，其中 $2\le p_1\le \lceil \frac{p}{2}\rceil -1$，那么

$\begin{array}{c}{r}_{B\left(p,q,l\right)}\left(u,v_j\right)-r_{B\left(p,q,l\right)}\left(x,u\right)=\frac{\left(p_1-1\right)\left(p-p_1+1\right)-\left(\lceil \frac{p}{2}\rceil -p_1\right)\left(\lfloor \frac{p}{2}\rfloor +p_1-2\right)}{p}\\ \le \frac{\left(p-\lceil \frac{p}{2}\rceil +\lfloor \frac{p}{2}\rfloor \right)\left(\lceil \frac{p}{2}\rceil -1\right)-\lceil \frac{p}{2}\rceil \left(2-\lfloor \frac{p}{2}\rfloor \right)-p-1}{p}\text{.}\end{array}$

因为

$\frac{\left(p-\lfloor \frac{p}{2}\rfloor +\lceil \frac{p}{2}\rceil \right)\left(\lfloor \frac{p}{2}\rfloor -1\right)-\lfloor \frac{p}{2}\rfloor \left(2-\lceil \frac{p}{2}\rceil \right)-p-1}{p}=\frac{\left(p-\lceil \frac{p}{2}\rceil +\lfloor \frac{p}{2}\rfloor \right)\left(\frac{p}{2}-1\right)-\lceil \frac{p}{2}\rceil \left(2-\lfloor \frac{p}{2}\rfloor \right)-p-1}{p}$，

所以有

$\begin{array}{c}{H}_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)\le \left(q+l-1\right)\frac{\left(p-\lfloor \frac{p}{2}\rfloor +\lceil \frac{p}{2}\rceil \right)\left(\lfloor \frac{p}{2}\rfloor -1\right)-\lfloor \frac{p}{2}\rfloor \left(2-\lceil \frac{p}{2}\rceil \right)-p-1}{p}\\ +\frac{\left(p+q+l-1\right)\lfloor \frac{p}{2}\rfloor \lceil \frac{p}{2}\rceil }{p}+M\text{.}\end{array}$

情况4. $v_j$ 和x都在 $C_q$ 上。同情况3讨论类似，我们有

$\begin{array}{c}{H}_{B_{n,v_j}\left(p,l,q\right)}\left(x,y\right)\le \left(p+l-1\right)\frac{\left(q-\lfloor \frac{q}{2}\rfloor +\lceil \frac{q}{2}\rceil \right)\left(\lfloor \frac{q}{2}\rfloor -1\right)-\lfloor \frac{q}{2}\rfloor \left(2-\lceil \frac{q}{2}\rceil \right)-q-1}{p}\\ +\frac{\left(p+q+l-1\right)\lfloor \frac{q}{2}\rfloor \lceil \frac{q}{2}\rceil }{q}+M\text{.}\end{array}$

4. $\phi \left(G\right)$ 的最小值

引理4.1. 设 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 和 $G_s=B\left(T_1,\cdots ,T_{i-1},K_{1,n_i-1},T_{i+1},\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，如果x是 $T_i$ 和 $K_{1,n_i-1}$ 中的一个悬挂点，且 $j\ne i$ 时，y是 $T_j$ 中的一个悬挂点，那么 $H\left(x,y\right)\ge H_{G_s}\left(x,y\right)$ 和 $H\left(y,x\right)\ge H_{G_s}\left(y,x\right)$。

证明：如果 $\left|V\left(T_i\right)\right|\le 2$，那么结论成立。我们假设 $\left|V\left(T_i\right)\right|\ge 3$。由引理2.4，我们有， $H\left(x,y\right)=H\left(x,v_i\right)+H\left(v_i,v_j\right)+H\left(v_j,y\right)$ 和 $H_{G_s}\left(x,y\right)=H_{G_s}\left(x,v_i\right)+H_{G_s}\left(v_i,v_j\right)+H_{G_s}\left(v_j,y\right)$。一方面， $H\left(x,v_i\right)\ge 1=H_{G_s}\left(x,v_i\right)$。另一方面，由引理3.2和引理2.1，我们有， $H\left(v_i,v_j\right)=H_{G_s}\left(v_i,v_j\right)$。由引理2.3，我们有， $H\left(v_j,y\right)=H_{G_s}\left(v_j,y\right)$。因此 $H\left(x,y\right)\ge H_{G_s}\left(x,y\right)$。

设w是G中x的唯一邻点。那么 $H\left(v_i,x\right)=H\left(v_i,w\right)+H\left(w,x\right)\ge H\left(w,x\right)=H_{G_s}\left(v_i,x\right)$。由引理2.4，我们有， $H\left(y,x\right)=H\left(y,v_j\right)+H\left(v_j,v_i\right)+H\left(v_i,x\right)\ge H_{G_s}\left(y,x\right)$。所以结论成立。

引理4.2. 设G和 $G_s$ 是引理4.1中的图。那么 $\phi \left(G_s\right)\le \phi \left(G\right)$。

证明：设x和y是两个顶点且有 $\phi \left(G_s\right)=H_{G_s}\left(x,y\right)$。由引理3.1，x和y要么是 $V\left(G_s\right)$ 中的悬挂点，要么是 $V\left(B\left(p,q,l\right)\right)$ 中度为2的点。我们考虑以下这三种情况。

情况1. 点 $x,y\notin V\left(K_{1,n_i-1}\right)$。由引理3.2，很容易看出 $\phi \left(G_s\right)=H_{G_s}\left(x,y\right)=H\left(x,y\right)\le \phi \left(G\right)$。

情况2. 点 $x,y\in V\left(K_{1,n_i-1}\right)$。由引理2.3，我们有 $H_{G_s}\left(x,y\right)=2\left(n+1\right)$。不失一般性的情况下，我们假设 $x,y\in V\left(T_i\right)$ 都是G中的悬挂点。设w是y的唯一的邻点。由引理2.4和引理2.3，我们有 $H\left(x,y\right)=H\left(x,w\right)+H\left(w,y\right)\ge 1+\left(2n+1\right)=\phi \left(G_s\right)$。

情况3. $x\in V\left(K_{1,n_i-1}\right)$ 或者 $y\in V\left(K_{1,n_i-1}\right)$。假设 $x\in V\left(K_{1,n_i-1}\right)$ 和 $y\in V\left(T_p\right)$，这里 $p\ne i$。不失一般性的情况下，我们假设 $x\in V\left(T_i\right)$ 和 $y\in V\left(T_p\right)$ 是G中对应的两个点。那么由引理4.1，有 $H\left(x,y\right)\ge H_{G_s}\left(x,y\right)$，这表明 $\phi \left(G\right)\ge H\left(x,y\right)\ge H_{G_s}\left(x,y\right)=\phi \left(G_s\right)$。因此结论成立。

引理4.3 设 $G=B\left(T_1,T_2,\cdots ,T_{p+q+l-2}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$ 和 $G^{\prime }=B\left(K_{1,n_1-1},\cdots ,K_{1,n_{p+q+l-2}-1}\right)\in {\mathcal{B}}_n\left(p,l,q\right)$，且对 $i=1,2,\cdots ,p+q+l-2$，有 $\left|V\left(T_i\right)\right|=n_i$。那么 $\phi \left(G^{\prime }\right)\le \phi \left(G\right)$。

证明：设x和y是 $G^{\prime }$ 中的两个点，且 $\phi \left(G^{\prime }\right)=H_{G^{\prime }}\left(x,y\right)$。由引理3.1，x和y要么是 $V\left(G^{\prime }\right)$ 中的悬挂点，要么是 $V\left(B\left(p,l,q\right)\right)$ 中度为2的点。我们考虑以下两种情况。

情况1. 假设 $x,y\in V\left(K_{1,n_i-1}\right)$ 是 $G^{\prime }$ 中的两个悬挂点。不失一般性的情况下，我们假设 $x,y\in V\left(T_i\right)$。由引理4.2的情况2，我们有 $H\left(x,y\right)\ge H_{G^{\prime }}\left(x,y\right)$。因此 $\phi \left(G\right)\ge H\left(x,y\right)\ge H_{G^{\prime }}\left(x,y\right)=\phi \left(G^{\prime }\right)$。

情况2. 假设 $x\in V\left(K_{1,n_i-1}\right)$ 和 $y\in V\left(K_{1,n_j-1}\right)$ 是 $G^{\prime }$ 中的两个点，这里 $1\le i\ne j\le p+q+l-2$。不失一般性的情况下，我们假设 $x\in V\left(T_i\right)$ 和 $y\in V\left(T_j\right)$ 是G中相对应的两个点，且有 $1\le i\ne j\le p+q+l-2$。由引理2.4和引理4.1，我们有， $H\left(x,y\right)=H\left(x,v_i\right)+H\left(v_i,v_j\right)+H\left(v_j,y\right)\ge H_{G^{\prime }}\left(x,y\right)$。因此 $\phi \left(G\right)\ge H\left(x,y\right)\ge H_{G^{\prime }}\left(x,y\right)=\phi \left(G^{\prime }\right)$。

令 $B_n^{v_1,\cdots ,v_{p+q+l-2}}\left(p,l,q\right)$ 是通过在 $B\left(p,l,q\right)$ 的 $v_i\left(1\le i\le p+q+l-2\right)$ 处连接 $n_i$ 个悬挂点的图。所以，对于任意的 $G\in {\mathcal{B}}_n\left(p,l,q\right)$，由定理3.7和引理4.3，我们有

$\phi \left(B_n^{v_1,\cdots ,v_{p+q+l-2}}\left(p,l,q\right)\right)\le \phi \left(G\right)\le \phi \left(B_{n,v_k}\left(p,l,q\right)\right)$。

即双圈图G的 $\phi \left(G\right)$ 达到它的上界时，当且仅当G中最多有一个非平凡的悬挂路径；达到它的下界时，当且仅当G中每一个悬挂树是个星图。

备注：目前的方法还无法确定图簇 ${\mathcal{B}}_n\left(p,l,q\right)$ 中双圈图G的 $\phi \left(G\right)$ 达到最小值时所对应的精确极图。