張 磊，張國志

（晉中學(xué)院數(shù)學(xué)學(xué)院，山西晉中030619）

0 引言

多處理機(jī)的互連網(wǎng)絡(luò)拓?fù)渫ǔＲ詧D為數(shù)學(xué)模型，其中圖的頂點(diǎn)代表處理機(jī)，邊代表處理機(jī)之間的直接通信聯(lián)系，故網(wǎng)絡(luò)拓?fù)涞男阅芸梢酝ㄟ^圖的性能和參數(shù)來衡量.為系統(tǒng)設(shè)計(jì)或者選擇網(wǎng)絡(luò)拓?fù)鋾r(shí)，一個(gè)基本的考慮是系統(tǒng)的可靠性，它對(duì)應(yīng)的連通性.但是用邊連通度來研究系統(tǒng)的可靠性不夠精確.在此背景下，1996年Fabrega和Foil［1］提出了k限制邊連通度的概念提出了限制邊連通度的概念.近年來，對(duì)于一般的正整數(shù)k，k限制邊連通度得到了廣泛的研究見文［2～4］.

1 準(zhǔn)備工作

在文中，我們主要考慮無向簡單圖.文中未給出的概念和符號(hào)見文［5］.設(shè)G是一個(gè)連通圖.用υ=表示G的階.若e=u，υ是G一條邊，則稱u與υ相鄰.設(shè)S為G中的一個(gè)邊集，對(duì)于G中任意一點(diǎn)u，用N（u）表示在G中與u的鄰點(diǎn)的集合，用d（u）=表示在G中與u相鄰的點(diǎn)的個(gè)數(shù).設(shè)W=υ0υ1υ2…υk是圖G的一條路.此時(shí)，若υ0=υk，則稱W為G中的圈.W中邊的數(shù)目稱為W的長.長為k的路（或圈）稱為k-路（或k-圈）.G的圍長g（G）是指G中最短圈的長.在G中頂點(diǎn)u和υ之間的距離d（u，υ）是最短（u，υ）-路的長.U，T 是 V（G）的非空子集，定義 d（U，T）=min｛d（u，υ）∶u∈U，υ∈T｝為 U，T 之間的距離.所謂二部圖是指一個(gè)圖，它的頂點(diǎn)集可以劃分為兩個(gè)非空子集V1和V2，使得任意的e=u，υ∈E（G）滿足=1；（V1，V2）稱為 G 的二分類.

定義 1.1對(duì)于具有二分類（V1，V2）的二部圖 G 中的兩個(gè)點(diǎn)集 U，T，令 Ui=U∩Vi，Ti=T∩Vi其中 i=1，2.稱滿足 d（U1，T1）=d（U2，T2）=k 的點(diǎn)集（U，T）對(duì)是（k，k）-距離極大的，如果不存在 U?U′，T?T′滿足 U≠U′或 T≠T′，使得 d（U′1，T′1）=d（U′2，T′2）=k.

1996年，為了精確研究并行計(jì)算機(jī)系統(tǒng)互連網(wǎng)絡(luò)拓?fù)涞目煽啃?，F(xiàn)àbrega和Foil［1］推廣了邊連通度λ（G），提出了k限制邊連通度 λ（kG）.

定義1.2［1］設(shè)G圖是連通圖，S?E（G）是G的邊割.如果G-S至少包含兩個(gè)連通分支且對(duì)于G-S的任意分支H都有V（H）≥k，那么稱滿足這樣條件的邊數(shù)最少的邊割為G的λk-割，G中所有λk-割所含邊數(shù)的下界稱為G的k限制邊連通度λ（kG）.

目前，k限制邊連通度得到了學(xué)者們的高度關(guān)注［2～4］.從現(xiàn)有研究成果來看，連通圖G的λ（kG）越大，G所對(duì)應(yīng)的網(wǎng)絡(luò)拓?fù)涞男阅茉礁撸?，7］.對(duì)正整數(shù)k，定義 ξ（kG）=min｛=k，G［X］連通，=V（G）X｝.如果λ（kG）=ξ（kG），那么稱G是極大k限制邊連通圖.

本文將給出二部圖中存在極大（4，4）-距離點(diǎn)集對(duì)與λ（5G）的關(guān)系.

2 主要結(jié)論

我們先給出以下將要用到的引理.

引理2.1［8］設(shè)G是λk-連通圖.當(dāng)k≥5時(shí)，如果υ＞k（k-1），則λk（G）≤ξk（G）.

引理2.2［9］令G是一個(gè)滿足λk（G）≤ξk（G）的λk-連通圖且［X，Y］是G的一個(gè)λk-割.若G［X］中存在一個(gè)k階連通子圖H滿足

則G是極大k限制邊連通的.

定理2.1設(shè)G是一個(gè)階υ＞20且δ（G）≥2的λ5-連通二部圖.若G的圍長g＞6且對(duì)于G中任意的（4，4）-距離極大點(diǎn)集對(duì)（U′，T′），在 G（U′∪T′）中存在同構(gòu)于 K1，4的連通分支，則 G 是極大 5 限制邊連通的.

證明用反證法.由引理2.1知，λ（5G）≤ξ（5G）.假設(shè)G不是極大5限制邊連通的.則 λ（5G）＜ ξ（5G）.設(shè)（V1，V2）為 G 的一個(gè)二分類矛盾.故

斷言X01≠? 且X02≠?.

用反證法.假設(shè)X01=?或X02=?.由于G［X］連通且X ≥6，因此G［X］中存在5階連通子圖H0.因?yàn)間 ＞ 6，所以對(duì)任意 x∈X1≥V（H0）有

由引理2.2知，G是極大5限制邊連通的，矛盾.

因此X0≠?.注意到X01=?或X02=?.不妨設(shè)假設(shè)X01=?.則X02≠?，即X=X11∪X02∪ X12.因?yàn)間＞6，所以H0為樹.因?yàn)镠0連通，所以

矛盾.斷言證明完成.

結(jié)合（2）式和H是G［U∪T］中的連通分支，可知對(duì)于任意一點(diǎn)u′∈X0V（H），都有

由引理2.2知，G是極大5限制邊連通的，矛盾.

矛盾.

情形2.2u?X.

情形3V（H）∩X=3.

注意到 H 同構(gòu)于 K1，4.故 2≤V（H）∩X，V（H）∩］≤3.記 d（u）=4，則 d（v）=d（w）=d（y）=d（z）=1.

情形3.1u∈X.

矛盾.

情形3.2u?X.