二部图是极大5限制边连通的充分条件

张 磊，张国志

（晋中学院数学学院，山西晋中030619）

0 引言

多处理机的互连网络拓扑通常以图为数学模型，其中图的顶点代表处理机，边代表处理机之间的直接通信联系，故网络拓扑的性能可以通过图的性能和参数来衡量.为系统设计或者选择网络拓扑时，一个基本的考虑是系统的可靠性，它对应的连通性.但是用边连通度来研究系统的可靠性不够精确.在此背景下，1996年Fabrega和Foil［1］提出了k限制边连通度的概念提出了限制边连通度的概念.近年来，对于一般的正整数k，k限制边连通度得到了广泛的研究见文［2～4］.

1 准备工作

在文中，我们主要考虑无向简单图.文中未给出的概念和符号见文［5］.设G是一个连通图.用υ=表示G的阶.若e=u，υ是G一条边，则称u与υ相邻.设S为G中的一个边集，对于G中任意一点u，用N（u）表示在G中与u的邻点的集合，用d（u）=表示在G中与u相邻的点的个数.设W=υ0υ1υ2…υk是图G的一条路.此时，若υ0=υk，则称W为G中的圈.W中边的数目称为W的长.长为k的路（或圈）称为k-路（或k-圈）.G的围长g（G）是指G中最短圈的长.在G中顶点u和υ之间的距离d（u，υ）是最短（u，υ）-路的长.U，T 是 V（G）的非空子集，定义 d（U，T）=min｛d（u，υ）∶u∈U，υ∈T｝为 U，T 之间的距离.所谓二部图是指一个图，它的顶点集可以划分为两个非空子集V1和V2，使得任意的e=u，υ∈E（G）满足=1；（V1，V2）称为 G 的二分类.

定义 1.1对于具有二分类（V1，V2）的二部图 G 中的两个点集 U，T，令 Ui=U∩Vi，Ti=T∩Vi其中 i=1，2.称满足 d（U1，T1）=d（U2，T2）=k 的点集（U，T）对是（k，k）-距离极大的，如果不存在 U⊆U′，T⊆T′满足 U≠U′或 T≠T′，使得 d（U′1，T′1）=d（U′2，T′2）=k.

1996年，为了精确研究并行计算机系统互连网络拓扑的可靠性，Fàbrega和Foil［1］推广了边连通度λ（G），提出了k限制边连通度 λ（kG）.

定义1.2［1］设G图……