劉愛霞，原 軍，吳紅梅(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

多處理機網(wǎng)絡(luò)和通信網(wǎng)絡(luò)能很容易的用一個圖來模擬，其中頂點集對應(yīng)處理機或交換機，邊集對應(yīng)通信線路。在網(wǎng)絡(luò)設(shè)計中一個最基本的問題就是網(wǎng)絡(luò)的可靠性。網(wǎng)絡(luò)的可靠性可以通過圖的連通度來度量，該網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)所對應(yīng)的圖的邊連通度越大，網(wǎng)絡(luò)越可靠。然而，具有相同邊連通度的圖可靠性卻不一定相同。為了更精確的度量圖的可靠性，Esfahanian和Hakimi[1]提出了限制邊連通度的概念。最近的研究結(jié)果表明限制邊連通度越大，網(wǎng)絡(luò)越可靠，該結(jié)論已被王應(yīng)前和李喬在文獻[2]中證明。研究圖的限制邊連通度有助于對現(xiàn)在流行的互連網(wǎng)絡(luò)的可靠性進行科學(xué)的評價，有很多關(guān)于圖的限制邊連通度的研究，見文獻[3]-文獻[8]。

當(dāng)一個圖中不含有三角形的時侯，這個圖就被稱作是無三角圖。無三角圖在互連網(wǎng)絡(luò)設(shè)計方面有非常廣泛的應(yīng)用。因此，為了更好地度量互連網(wǎng)絡(luò)可靠性，對無三角圖的限制邊連通度進行研究就顯得非常必要。本文研究并證明了λ′-最優(yōu)無三角圖的最小邊度的充分條件。而且，舉例說明本文結(jié)果是最好的。

1 預(yù)備知識

本文所討論的圖均為無向圖，先給出相關(guān)的術(shù)語和記號，文中未定義的術(shù)語和記號參見文獻[9]。

2 主要結(jié)果及其證明

張昭在2007年給出了一個λ′-最優(yōu)無三角圖的最小邊度充分條件：

定理1設(shè)G是n階連通的無三角圖，最小度δ(G)≥2.若ξ(G)≥n-1，則G是λ′-最優(yōu)的。

本文給出比這個定理更好的一個充分條件。首先需要文獻[1]中的一個定理。

引理1對每一個n≥4階的連通圖G，除星圖K1,n-1外，都是λ′-連通的，且滿足:

λ(G)≤λ′(G)≤ξ(G)

在給出本文主要結(jié)論之前，先證明一個重要引理。

ξ(G)≤|[{x,y},V(G){x,y}]|=|S(x)|+

|S(y)|+|[{x,y},U{x,y}]|≤|S(x)|+

|S(y)|+|U{x,y}|≤|S(x)|+|S(y)|+

(因為G是無三角圖)

這與λ′(G)<ξ(G)的假設(shè)矛盾。定理證畢。

下面給出本文的主要結(jié)論及證明。

定理2設(shè)G是一個n階的連通無三角圖，最小度δ(G)≥2.若最小邊度滿足:

則G是λ′-最優(yōu)的。

因此，U*是G的一個獨立集。設(shè)u是U*中的一個點，則由U*的定義知|S(u)|=0.令v是NG[U](u)中的點，并且|S(v)|=min{|S(w)|∶w∈NG[U](u)}(因為<δ(G)≥2，所以v點是存在的)。令:

A1={w∈U{v}∶w與u相鄰}，

A2={w∈U{u}∶w與v相鄰}.

由于G是無三角圖，且邊uv∈E(G)，推出A1∩A2=φ.記ai=|Ai|，i=1,2,則：

ξ(G)≤d(u)+d(v)-2=|S(v)|+a1+a2

(1)

因為|S(v)|=min{|S(w)|∶w∈NG[U](u)}，即對任意的點x∈A1，均滿足|S(x)|≥|S(v)|，所以有:

(2)

將式(1)、式(2)與假設(shè)|S|<ξ(G)結(jié)合，得|S(v)|+a1+a2≥ξ(G)>|S|>a1|S(v)|+|S(v)|，即:

a1|S(v)|

注意到δ(G)≥2，|S(u)|=0且d(u)=|S(u)|+a1+1=a1+1.由此推出a1≥1.因此:

(3)

顯然，|U|≥a1+a2+2，即|U|-2≥a1+a2，

將其與式(1)結(jié)合，可得ξ(G)≤|S(v)|+a1+a2≤|S(v)|+|U|-2，再與式(3)結(jié)合可得到:

因此:

由定理2可以得出以下推論：

由定理2知，G是λ′-最優(yōu)的。證明完畢。

參考文獻：

[1] ESFAHANIAN A H，HAKIMI S L.On computing a conditional edge-connectivity of a graph[J].Information Proceeding Letters，1988，27(4)：165-199.

[2] 王應(yīng)前，李喬.直徑為2的圖的超級邊連通性質(zhì)[J].上海交通大學(xué)學(xué)報，1999，33 (6)：646-649.

[3] BALBUENA C，CARMONA A，F(xiàn)BREGA J，F(xiàn)OIL M A.Superconnectivity of bipartite digraphs and Graphs[J].Discrete Mathematics，1999，197-198：61-75.

[4] BALBUENA C，GARCA-VZQEZ P，MARCOTE X.Sufficient conditions forλ′-optimality in graphs with girth[J].Journal of Graph Theory，2006，52：73-86.

[5] HELLWIG A，VOLKMANN L.Sufficient conditions for graphs to beλ′-optimal，super-edge-connected，and maximally edge-connected[J].Journal of Graph Theory，2005，48：228-246.

[6] LI Q L，LI Q.Super edge connectivity properties of connected edge symmetric graphs[J].Networks，1999，33：147-159.

[7] MENG J X.Optimally super-edge-connected transitive graphs[J].Discrete Mathematics，2003，260：39-248.

[8] 吳紅梅，原軍.超級λ3-最優(yōu)二部圖的充分條件[J].太原科技大學(xué)學(xué)報，2011，32(40)：332-336.

[9] BONDY J A，MURTY U S R.Graph Theory with Applications[M].New York：The Macmillan Press Ltd，1976.

[10] ZHANG Z.Sufficient conditions for restricted-edge-connectivity to be optimal[J].Discrete Mathematics，2007，307：2891-2899.