二部圖是極大5限制邊連通的充分條件

張 磊，張國志

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

0 引言

多處理機的互連網(wǎng)絡拓撲通常以圖為數(shù)學模型，其中圖的頂點代表處理機，邊代表處理機之間的直接通信聯(lián)系，故網(wǎng)絡拓撲的性能可以通過圖的性能和參數(shù)來衡量.為系統(tǒng)設計或者選擇網(wǎng)絡拓撲時，一個基本的考慮是系統(tǒng)的可靠性，它對應的連通性.但是用邊連通度來研究系統(tǒng)的可靠性不夠精確.在此背景下，1996年Fabrega和Foil［1］提出了k限制邊連通度的概念提出了限制邊連通度的概念.近年來，對于一般的正整數(shù)k，k限制邊連通度得到了廣泛的研究見文［2～4］.

1 準備工作

在文中，我們主要考慮無向簡單圖.文中未給出的概念和符號見文［5］.設G是一個連通圖.用υ=表示G的階.若e=u，υ是G一條邊，則稱u與υ相鄰.設S為G中的一個邊集，對于G中任意一點u，用N（u）表示在G中與u的鄰點的集合，用d（u）=表示在G中與u相鄰的點的個數(shù).設W=υ0υ1υ2…υk是圖G的一條路.此時，若υ0=υk，則稱W為G中的圈.W中邊的數(shù)目稱為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年，為了精確研究并行計算機系統(tǒng)互連網(wǎng)絡拓撲的可靠性，F(xiàn)àbrega和Foil［1］推廣了邊連通度λ（G），提出了k限制邊連通度 λ（kG）.

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

目前，k限制邊連通度得到了學者們的高度關注［2～4］.從現(xiàn)有研究成果來看，連通圖G的λ（kG）越大，G所對應的網(wǎng)絡拓撲的性能越高［6，7］.對正整數(shù)k，定義 ξ（kG）=min｛=k，G［X］連通，=V（G）X｝.如果λ（kG）=ξ（kG），那么稱G是極大k限制邊連通圖.

本文將給出二部圖中存在極大（4，4）-距離點集對與λ（5G）的關系.

2 主要結論

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

引理2.1［8］設G是λk-連通圖.當k≥5時，如果υ＞k（k-1），則λk（G）≤ξk（G）.

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

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

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

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

斷言X01≠? 且X02≠?.

用反證法.假設X01=?或X02=?.由于G［X］連通且X ≥6，因此G［X］中存在5階連通子圖H0.因為g ＞ 6，所以對任意 x∈X1≥V（H0）有

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

因此X0≠?.注意到X01=?或X02=?.不妨設假設X01=?.則X02≠?，即X=X11∪X02∪ X12.因為g＞6，所以H0為樹.因為H0連通，所以

矛盾.斷言證明完成.

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

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

矛盾.

情形2.2u?X.

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

注意到 H 同構于 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.