1. 引言
本文只考虑简单连通图
,其中
是G的顶点集,
是G的边集。对两个点
,x和y之间的距离用
表示。对于任意点
,与x相关联的边的数目叫做x在G的度,记作
。
在 [1] 中,Klein和Randić提出了一个图上的新的距离函数——有效电阻。把图G中的每条边看作电阻值为1的电阻,点x和y之间的电阻值,叫做点x和y之间的有效电阻,记为
。显然,当图G是树时,
。我们把
叫做点x的weighted resistance centrality [2]。
给定一个图G,通常将G上的随机游走定义为马尔可夫链。图G上的随机游走中,顶点x跳到邻点的概率为
,那么G中从顶点x到顶点y的hitting time [3]
是随机游走中步数的期望值。图G的hitting time定义为
。
Zhang和Li [4] 得到了树中
的上界和下界,并且表明星图达到下界以及路径达到上界。此外,Zhu和Zhang [5] [6] 得到了单圈图中
的上界和下界,并且确定了极图。本文将继续研究有关问题。我们将刻画双圈图中
的上界和下界所对应的极值图。
2. 预备知识
双圈图G是满足
的简单连通图。本文只考虑基本型为
-型
的双圈图。设
是一个双圈图,其两个圆
和
之间有一条长为l的路径。当
时,路径
和圆
和
的交点分别为u和v。当l = 1时,我们仍然使用u = v来表示圆
和
的交点。
图簇
被定义为阶数为n的图的集合,这些图是由在
顶点处悬挂树得到的。在本文中,我们使用
来表示
的顶点,每个挂在顶点
的树用
表示,其点的个数用
表示,图G可用
表示,其中
。请注意,我们将使用
表示悬挂在
点的树。
我们现在列出以下重要引理。
引理2.1. [2] 设T是n个点的树,对任意的两个点
,有
。
引理2.2. [7] 设G是边数为m的简单连通图。那么,对于
,有
。
引理2.3. [8] 设G是一个n个点的简单连通图,点
。如果存在唯一的一条路径
,其中
和
,且对于
,
是
包含
的部分的边数,
和
,那么有
。
引理2.4. [1] 设z是连通图G的割点,x,y是G-z的不同部分中的两个顶点。那么有
。而且,如果G中存在一条唯一的路径
,那么有
。
引理2.5. [5] 设G是圈长为g且点数为n的单圈图,那么
。
引理2.6. [9] 设
和
。那么
。
令
,对任意的
,
,由引理2.2和2.6,显然有
(1)
3.
的最大值
引理3.1. 令
。如果
中存在两个顶点x,y,使得
,则x和y要么是
中的悬挂点,要么是
中度为2的点。
证明:假设
中的点y既不是
中的悬挂点,也不是
中度为2的点,那么它一定是一个割点。由引理2.4,则存在点
使得
。因此,
不是最大的,这与条件相矛盾。因此,y要么是
中的悬挂点,要么是
中度为2的点。类似地,我们可以证明x要么是
中的悬挂点,要么是
中度为2的点。
引理3.2. 设
和
,如果
和
,其中
,
,
,且
,
,那么
。
证明:在不失一般性的前提下,假设
。由引理2.4,我们有
和
。显然,由引理2.3,有
和
。那么由式子(1),我们有
。
这就得出了我们要的结论。
引理3.3. 设
。如果
中存在一个悬挂点w,其中
是从G中删除w的关联边并添加一条连接点w和
中的一个顶点的边而得到的图,那么对于任意的两个点
和
且
,有
。
证明:假设在
中
。由式子(1),我们有
这就得出了我们要的结论。
引理3.4. 设
,存在两个点
和
,
,且有
。设
,且
,
,对于
,有
。设
,且
,
,对于
,有
。假设点x和y分别在
和
上,那么它们要不是悬挂点,要不
中度为2的点,且有
和
。
证明:由引理3.1,我们知道x和y要不是
中的悬挂点,要不是
中度为2的点。我们考虑下面这三种情况。
情况1. x和y都是
中度为2的点。
由引理3.2,我们有
和
。
情况2. 假设
,
是一个悬挂点和
。
此外,我们有
是
中的一个悬挂点。由引理2.4,我们有
和
。根据hitting time的定义和引理2.1,我们有
。此外,由引理3.2,我们有
。此外,由定理2.3,很容易看出,
。因此,
。
情况3. 假设
,
是一个悬挂点和
。
此外,我们有
是
中的一个悬挂点。由引理2.4,我们有
。显然,
和
。因此,我们只需要比较
和
。设P是从点
到点y的唯一路径,且
,
和
。对于
,设
是G中删除
和
且包含点
的子图,其中
和
。设
是
的边数,那么
。由引理2.3,我们有
和
。因此,
其中
。如果
,那么x是
中度为2的一个点。因此
。
设
,那么对于
,G中存在两个顶点
和
,使得
。
设
中有
和
,且有
和
,对于
,有
。
设
中有
,且对于
,有
。
设
中有
,
,且对于
,有
。
设
中有一棵唯一的树,
或者
,并且对于
或者
,有
。
推论3.5.
。
证明:由引理3.3,3.4,结论显然成立。
引理3.6. 设x和y是
中的两个顶点,且有
,
,
。那么
。
证明:由引理3.1,x和y要么是悬挂点要么是圈上度为2的点。我们考虑以下四种情况。
情况1. x和y都是
的圈上度为2的点。由式子(1),我们有
当x和y都固定时,
也是个定值。因为
所以我们有
。
情况2. x是
的悬挂点,记作
,也就是i = k,和y是
的圈上度为2的点。由式子(1),我们有
当x和y都固定时,
也是个定值。但是
,
这与G的选择所矛盾,所以
。
情况3. y是
中的一个悬挂点,记作
,也就是j = z,和x是
的圈上度为2的点。由式子(1),我们有
当x和y都固定时,
也是个定值。但是
这与G的选择所矛盾,所以
。
情况4.
和
都是
的悬挂点,也就是i = k,j = z。由式子(1),有
当x和y都固定时,
也是个定值。但是
,这与G的选择所矛盾,所以
。所以结论成立。
又一次令
是通过在
的
处连接
的一个端点的图。设
和
定理3.7.
。
证明:设x和y是
中的两个点并且
,
,那么
。由引理3.1,点x和y要么是悬挂点,要么是圈上度为2的点。由推论3.5,我们知道x或者y是悬挂点。如果x是一个悬挂点并且
是
中的圈上度为2的点,那么假设
是一个悬挂点且
是
中的圈上度为2的点,就有
所以,y是一个悬挂点且
是
中的圈上度为2的点,那么
。假设
和
,
,
,那么有
设
。由二次函数的性质,我们知道
取到它的最大值当且仅当
或者
,这如同
。所以
是
中的圈上度为2的点,且
。对点
和x的具体位置,我们分以下几种情况讨论。
情况1.
和
。
由引理2.5,有
。所以我们有
情况2.
和
。同情况1讨论类似,我们有
情况3.
和x都在
上。那么
如果路径x-u-vj的长度是
和路径u-x-vj的长度是
,其中
,那么
如果路径x-u-vj的长度是
和路径u-x-vj的长度是
,其中
,那么
因为
,
所以有
情况4.
和x都在
上。同情况3讨论类似,我们有
4.
的最小值
引理4.1. 设
和
,如果x是
和
中的一个悬挂点,且
时,y是
中的一个悬挂点,那么
和
。
证明:如果
,那么结论成立。我们假设
。由引理2.4,我们有,
和
。一方面,
。另一方面,由引理3.2和引理2.1,我们有,
。由引理2.3,我们有,
。因此
。
设w是G中x的唯一邻点。那么
。由引理2.4,我们有,
。所以结论成立。
引理4.2. 设G和
是引理4.1中的图。那么
。
证明:设x和y是两个顶点且有
。由引理3.1,x和y要么是
中的悬挂点,要么是
中度为2的点。我们考虑以下这三种情况。
情况1. 点
。由引理3.2,很容易看出
。
情况2. 点
。由引理2.3,我们有
。不失一般性的情况下,我们假设
都是G中的悬挂点。设w是y的唯一的邻点。由引理2.4和引理2.3,我们有
。
情况3.
或者
。假设
和
,这里
。不失一般性的情况下,我们假设
和
是G中对应的两个点。那么由引理4.1,有
,这表明
。因此结论成立。
引理4.3 设
和
,且对
,有
。那么
。
证明:设x和y是
中的两个点,且
。由引理3.1,x和y要么是
中的悬挂点,要么是
中度为2的点。我们考虑以下两种情况。
情况1. 假设
是
中的两个悬挂点。不失一般性的情况下,我们假设
。由引理4.2的情况2,我们有
。因此
。
情况2. 假设
和
是
中的两个点,这里
。不失一般性的情况下,我们假设
和
是G中相对应的两个点,且有
。由引理2.4和引理4.1,我们有,
。因此
。
令
是通过在
的
处连接
个悬挂点的图。所以,对于任意的
,由定理3.7和引理4.3,我们有
。
即双圈图G的
达到它的上界时,当且仅当G中最多有一个非平凡的悬挂路径;达到它的下界时,当且仅当G中每一个悬挂树是个星图。
备注:目前的方法还无法确定图簇
中双圈图G的
达到最小值时所对应的精确极图。