极大4限制边连通图的充分条件

郝海霞,张 磊,徐子钧

(晋中学院数学学院,山西晋中030619)

所考虑的图都是无向简单图。文中出现而未定义的概念和记号参见文献[1]。设G=(V(G),E(G))是一个连通图。用ν=|V(G) |表示G的阶。若e=uv是G一条边,则称u与v相邻。设S为G中的一个边集,对于G中任意一点u,用N(u)表示在G中与u相邻的点的集合,用d(u)表示在G中与u相邻的点的数目。假设U是V(G)的一个非空子集。以U为顶点集,以G中两个端点均在U中的所有的边的集合为边集所组成的子图称为G的由U导出的子图,记为G[U];这时,也称G[U]为G的导出子图。图G中的一条路是指一 个有限非空序列W=v0e1v1e2v2…ekvk,它的项交替地为顶点和边,使得对 1 ≤i≤k,ei=vi-1vi,其中v0,v1,v2,…,vk-1,vk互不相同。称W是从v0到vk的一条路, 此时, 若v0=vk,则称W为G中的圈。W中边的数目称为W的长。长为k的路(或圈)称为k-路(或k-圈)。G的围长g(G)是指G中最短圈的长。若在G中顶点u和v是连通的,则u和v之间的距离d(u,v)是G中最短(u,v)-路的长。V1,V2是V(G)的非空子集V1,V2之间的距离定义为d(V1,V2)= min{d(u,v):u∈V1,v∈V2}。称满足d(V1,V2)=k的点集对V1,V2是k-距离极大的, 如果不存在顶点子集满 足使得对G的两个非空顶点子集X与Y,用[X,Y]表示G中一端点在X中另一端点在Y中的所有边组成的集合,X是V(G)的非空子集,G的边割是指形为[X,Y]的E(G)的子集,其中Y=V(G)X。

多处理机的互连网络拓扑常以图为数学模型,用图的顶点(即节点)代表处理机,用边来代表处理机之间的直接通信联系,因此网络拓扑的性能可以通过图的性能和参数来衡量。为系统设计或者选择网络拓扑时,一个基本的考虑是系统的可靠性,它对应图的连通性。但是用边连通度来研究系统的可靠性不够精确。在此背景下,1996 年FAbrega和Foil在文献[2]中提出了k限制边连通度的概念。

定义1设G是一个连通图,S⊆E(G)是G的一个边割。如果G-S的每个连通分支至少有k个顶点,那么称S是G的一个k限制边割。

称G的所有k限制边割中所含边数最少的边割为G的λk-割,λk-割所含的边数称为G的k限制边连通度,记为λk(G)。当k=2 时,通常称k限制边连通度为限制边连通度, 记为λ′(G)。应该指出,不是所有图都存在k限制边割。若G存在k限制边割,则称G为λk-连通图。近年来,对于一般的正整数k,k限制边连通度得到了广泛的研究,见文献［3-5］。从目前的研究结果来看,对于连通图G,人们相信λk(G)越大,G所对应的网络的可靠性就越好［6-8〕,因此人们希望图G的k限制边连通度尽可能地大。显然这需要λk(G)的一个上界。对正整数k,定义ξk(G)=min{[X,Y]:|X|=k,G[X]连通,Y=V(G)X}。

若λk(G)=ξk(G),则称G是极大k限制边连通的。

将给出极大4限制边连通图与围长和3-距离极大点集对的关系。

引理 1设G是λ4-连通图。若ν(G)≥11, 则λ4(G)≤ξ4(G)［9］。

引理2令G是一个满足λk(G)≤ξk(G)的λk-连通图且[X,Y]是G的一个λk-割。若G[X]中存在一个k阶连通子图H满足

则G是极大k限制边连通的[10]。

定理1设G是一个阶ν(G)≥11 的λ4-连通图。若G的围长g＞6 且对于G中任意3-距离极大点集对S,T,在G[S∪T]中都有阶为4 的连通分支,则G是极大4限制边连通的。

证明用反证法。假设G不是极大4 限制边连通 的 。 因 为ν(G)≥11,由 引 理 2.1,所 以λ4(G)≤ξ4(G)。 则λ4(G)＜ξ4(G)。设 [X,Y]是G的λ4-割。若 |X|=4 或 |Y|=4, 则有ξ4(G)≤| [X,Y] |=λ4(G), 矛盾。 故 |X|≥ 5 且 |Y|≥5 。设X1⊆X,Y1⊆Y是与[X,Y]中至少一条边相关联的点集。令X0=XX1,,Y0=YY1。

断言X0≠φ且Y0≠φ。

假设X0=φ, 则X1=X, 即对任意的u∈X有|N(u)∩Y|≥1。由于|X|≥5, 因此在G[X]中存在 一个4 阶连通子图H0。因为g＞6,所以对于任意的u∈XV(H0)有|N(u)∩V(H0)|≤1。故我们有

由引理2知,G是极大4限制边连通的,矛盾。

同理可得Y0≠φ。断言证明完成。

由于d(X0,Y0)≥3, 因此G中存在一个3-距离极大点集对S,T,使得X0⊆S且Y0⊆T。由题设知,在G[S∪T]中存在阶为4的连通分支H。由于G的围长g＞6,因此H为一条3-路或者同构于K1,3,且对于任意的u∈V(G)V(H)有

令V(H)={w0,w1,w2,w3}。由于G的围长g＞6,因此

其中 0 ≤i,j≤ 3,i≠j。

因为H是G[S∪T]中的连通分支,所以对于任意u∈(X0∪Y0)V(H), 都有 |N(u)∩V(H)|=0 。此时,对 于任意 的v∈V(H), 有N(v)V(H)⊆X1∪Y1。 由X,Y的对称性, 下面考虑 |V(H)∩X|≥|V(H)∩Y|的情形。

情形1|V(H)∩X|=4。

注 意 到 对 于 任 意u∈(X0∪Y0)V(H), 都 有|N(u)∩V(H)|=0。结合(1)式,对于XV(H)中任意一点x,都有|N(x)∩V(H)|≤|N(x)∩Y|。因此我们有

由引理2知,G是极大4限制边连通的,矛盾。

情形2|V(H)∩X|=3。

（1）H是一条3-路。

不妨设H=w0w1w2w3。因 |V(H)∩X|=3 所以|V(H)∩Y|=1。

|{w0,w3}∩X|=1。

由对称性,我们不妨设w0∈X。因为|V(H)∩X|=3,所以w0,w1,w2∈X。由于G的围长g＞6,因此 (N(w0)∪N(w1)∪N(w2))∩X1中的点与N(w3)∩Y1中的点不相邻。结合(2)式,我们有

矛盾。

|{w1,w2}∩X|=1。

由对称性, 我们不妨设w1∈X。因为|V(P)∩X|=3, 所以w0,w1,w3∈X。由于G的围长g＞ 6, 因此 (N(w0)∪N(w1)∪N(w3))∩X1中的点与N(w2)∩Y1中的点不相邻。因为w1w2,w2w3∈[X,Y], 结合(2)式和(3)式,所以我们有

（2）H≅K1,3。

不妨设dH(w0)=3。

|{w1,w2,w3}∩X|=2。

由对称性, 我们不妨设w3∈Y。因为 |V(H)∩X|=3,所以w0,w1,w2∈X。由于G的围长g＞ 6,因此 (N(w0)∪N(w1)∪N(w2))∩X1中的点与N(w3)∩Y1中的点不相邻。因为w0w3∈[X,Y],结合(2)式和(3)式,所以我们有

矛盾。

w0∈Y。

因为 |V(H)∩X|=3, 所以w1,w2,w3∈X。由于G的围长g＞6, 因此 (N(w1)∪N(w2)∪N(w3))∩X1中的点与N(w0)∩Y1中的点不相邻。因为w0w1,w0w2,w0w3∈[X,Y], 结合(2)式和(3)式,所以我们有

矛盾。

情形3|V(H)∩X|=2。

（1）H是一条3-路。

不妨设H=w0w1w2w3。因为 |V(H)∩X|=2, 所以|V(H)∩Y|=2。

（2）|{w0,w3}∩X|=1。

由对称性,我们不妨设w0∈X。因为V(H)∩|X|=2,所以w0,w1∈X或w0,w2∈X。由于G的围长g＞ 6,因此当w0,w1∈X时, (N(w0)∪N(w1))∩X1中的点与N(w2)∪N(w3)∩Y1中的点不相邻。注意到w1,w2∈[X,Y]。结合(2)式和(3)式,我们有

矛盾。

当w0,w2∈X时,由 于G的 围 长g＞6,因 此(N(w0)∪N(w2))∩X1中的点与N(w1)∪N(w3)∩Y1中的点不相邻。注意到w0w1,w1w2,w2w3∈[X,Y]。结合⑵式和(3)式,我们有

矛盾。

|{w0,w3}∩X|=0

或|{w0,w3}∩X|=2。

由对称性, 我们不妨设|{w0,w3}∩X|=0。因为|V(H)∩X|=2,所以w1,w2∈X。由于G的围长g＞6,因此N(w1)∪N(w2)∩X1中的点与 (N(w0)∪N(w3))∩Y1中的点不相邻。注意到w0w1,w2w3∈[X,Y]。结合⑵式和(3)式,我们有

矛盾。

2H≅K1,3。

不妨设dH(w0)=3 。因为 |V(H)∩X|=2, 所以|{w1,w2,w3}∩X|=2 或|{w1,w2,w3}∩Y|=2。由对称性,我们 不 妨设 |{w1,w2,w3}∩X|=2 且w3∈Y。易 知w1,w2∈X且w0∈Y。 由 于G的围 长g＞ 6, 因 此(N(w1)∪N(w2))∩X1中的点与 (N(w0)∪N(w3))∩Y1中的点不相邻。注意到w0w1,w0w2∈[X,Y]。

结合⑵式和(3)式,我们有

矛盾。