基于广义Randić指数的限制边连通性的研究

崔艺兰，欧见平

（五邑大学 数学与计算科学学院，广东 江门 529020）

为了更准确估计和比较网络的可靠性，文献[7-8]介绍了m限制边割和m限制边连通度的概念:图G的边割S是一个m限制边割，如果G-S的每个连通分支都至少含有m个点. 所有m限制边割中所含的最小边数称为图G的m限制边连通度，用λm(G)表示，或简写为λm. 如果连通图G含有m限制边割，则称它是λm连通的. 令，其中表示图G中只有一个端点在X的边的集合，简写为. 如果，则图G是λm最优的或极大m限制边连通的. 注意到当m= 1时，是边连通度；当m= 2时，是限制边连通度，也常表示为λ＇；当m= 3时是3 限制边连通度λ3. 极大3 限制边连通在网络设计的可靠性中发挥着重要的作用，一些极大3 限制边连通的充分条件可以在文献[9-10]中得到. 极大m限制边连通也取得了丰硕的成果，读者可参考文献[7-8]等.

Li 等[11]在2005 年定义了零阶广义Randić 指数：，其中α是实数，d(v) 是点v的度. 特别地，当α=-1 时，，即为图G的逆度. 许多研究者给出了基于零阶广义Randić 指数，阶数和最小度的最优λ(G)图和超级λ(G)图的充分条件[12-16]. 郭利涛等[17-19]还给出了关于R(G) ,δ(G) ,ξ(G)和n的函数的图是最优λ2和最优λ3的充分条件. 本文将他们的结论推广到限制边连通图上，分别考虑在一定条件下，基于零阶广义Randić 指数分别给出了围长g≥ 5、δ≥2的图是λ2最优及g≥ 6、δ≥ 2的图是λ3最优的充分条件. 对于未说明的其他符号和术语，我们采用文献[20]中的符号与术语.

1 预备引理

为了得到主要结论，我们将列出用于后面证明的一些引理.

引理1[12]设实数α＜0或者α＞ 1且x1,x2, … ,xp和A为正实数使得，则.如果x1,x2, … ,xp和A为正整数且A=ap+b，其中a,b是整数且0≤b＜p，则.

引理2[13]设实数0＜α＜ 1且x1,x2, … ,xp和A为正实数使得，则. 如果x1,x2, … ,xp和A为正整数且A=ap+b，其中a,b是整数且0≤b＜p，则.

以下这个引理来自凸函数和凹函数的定义.

引理3[17]设 Φ (x)是［L,R］上的连续函数且l+r=L+R，其中l,r∈［L,R］. 则

引理4[18]设G是围长大于等于5 的λ2连通图，且δ(G) ≥ 2，则存在一个λ2割［X,Y］，其中两个不交点集且［X,Y］ =λ2. 如果λ2＜ξ，则.

引理 5[19]设G是λ3连通围长大于等于 6 的图，且δ(G) ≥ 2. 如果，则存在一个λ3割［X,Y］，其中两个不交点集，使得.

2 极大限制边连通性

接下来我们考虑在一定条件下，图G是2λ最优及3λ最优的充分条件.

定理1设G是围长g(G) ≥5 的2λ连通n阶图且最小度δ≥2 .

1）若α≤-1 且，则.

2）若 -1 ＜α＜ 0且，则.

3）若1＜α≤ 2且，则.

证明反设，则图G存在一个最小2 限制边割S=[X,Y]，其中,X,Y是两个不交的点集使得，且. 根据引理 4 可知，，所以. 不失一般性，设图G的最小度为δ的一个点.

由于X中的每个点至多能与X中的个点相连，且X中的点仅与Y中的点有λ2条边相连.则

同理，

由引理1，可得

所以，

当α≤- 1时，，且. 由于，容易验证 当t＞1,α≤-1 时，，所以 此时g(t)为凹函数. 又由假 设，则有

矛盾.

当 - 1＜α＜ 0时，，且. 由于，容易验证当t＞ 1, -1＜α＜ 0时，，所以此时g(t)也为凹函数. 又由假设，则有

矛盾.

当1＜α≤ 2时，，且. 同 样 容 易 验 证 当t＞1,1＜α≤ 2时，，所以g(t)为凹函数. 又由假设，得

定理 2设G是围长g(G) ≥ 5的λ2连通n阶图且最小度δ≥ 2. 若0＜α＜ 1且，则.

证明反设，则图G存在一个最小2 限制边割S=[X,Y]，其中,X,Y是两个不交的点集使得，且. 根据引理 4 可知，，所以. 不失一般性，设图G的最小度为δ的一个点.

由于X中的每个点至多能与X中的X- 1个点相连，且X中的点仅与Y中的点有λ2条边相连.则

由引理2，可得

同理，

由引理2，可得

所以，.因为0＜α＜ 1，所以. 令函数，容易验证当，所以此时g(t)为凸函数，根据引理3，可得

矛盾. 定理证毕.

定理3设G是围长g(G) ≥ 6且最小度δ(G) ≥ 2的λ3连通n阶图.

1）若α≤-1 且，则.

2）若 -1 ＜α＜ 0且，则.

3）若1＜α≤ 2且，则.

证明反设，则图G存在一个最小3 限制边割S=[X,Y]，其中,X,Y是两个不交的点集使得，且. 根据引理 5 可知，，所以. 不失一般性，设图G的最小度为δ的点.

由于X中的每个点至多能与X中的个点相连，且X中的点仅与Y中的点有λ3条边相连.则

由引理1，可得

同理，

由引理1，可得

当α≤-1 时，容易验证g(t)为凹函数且

矛盾.

当 -1 ＜α＜ 0时，容易验证g(t)也为凹函数且

矛盾.

当1＜α≤ 2时，容易验证g(t)为凹函数且

矛盾. 定理证毕.

定理4设G是围长g(G) ≥ 6且最小度δ(G) ≥ 2的n阶λ3连通图. 若0＜α＜ 1且,则.

证明反设，则图G存在一个最小3 限制边割S=[X,Y]，其中,X,Y是两个不交的点集使得，且. 根据引理 5 可知，，所以. 不失一般性，设图G的最小度为δ的一个点.

由于X中的每个点至多能与X中的个点相连，且X中的点仅与Y中的点有λ3条边相连.则

由引理2，可得

同理

由引理2，可得

因为0＜α＜ 1，所以

且

矛盾. 定理证毕.