λ′-最優(yōu)無(wú)三角圖的最小邊度充分條件

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

本文給出比這個(gè)定理更好的一個(gè)充分條件。首先需要文獻(xiàn)[1]中的一個(gè)定理。

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

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

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

ξ(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)|+

(因?yàn)镚是無(wú)三角圖)

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

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

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

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

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

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

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

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

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

(1)

因?yàn)閨S(v)|=min{|S(w)|∶w∈NG[U](u)}，即對(duì)任意的點(diǎn)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)的。證明完畢。

參考文獻(xiàn)：

[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的圖的超級(jí)邊連通性質(zhì)[J].上海交通大學(xué)學(xué)報(bào)，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] 吳紅梅，原軍.超級(jí)λ3-最優(yōu)二部圖的充分條件[J].太原科技大學(xué)學(xué)報(bào)，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.