超級(jí)-λ′無三角圖的度和充分條件

原軍， 劉愛霞

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

摘要：設(shè)S是連通圖G的一個(gè)邊割。 若G-S不包含孤立點(diǎn)，則稱S是G的一個(gè)限制邊割。 如果圖G的每個(gè)最小限制邊割恰好分離出圖G的一條邊，則稱圖G是超級(jí)限制邊連通的，簡稱超級(jí)-λ′的。 設(shè)G是一個(gè)階n≥4的連通無三角圖。 本文證明了若G中任意滿足dist(u,v)=2的點(diǎn)對(duì)u,v∈V(G)有d(u)+d(v)≥2+3，則G是超級(jí)-λ′的。 最后，舉例說明該結(jié)論是最好的。

關(guān)鍵詞：限制邊連通度；超級(jí)-λ′圖；無三角圖

收稿日期：2015-03-11

基金項(xiàng)目：國家數(shù)學(xué)天元基金(11126076)；國家青年科學(xué)基金(61402317)；山西省青年自然科學(xué)基金(2012021001-2)

作者簡介：原軍(1979-)，男，副教授，主要研究方向?yàn)閳D論及其應(yīng)用。

中圖分類號(hào)：O157.5文獻(xiàn)標(biāo)志碼：A

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

互連網(wǎng)絡(luò)的可靠性是互連網(wǎng)絡(luò)設(shè)計(jì)中一個(gè)最基本而又重要的研究課題。互連網(wǎng)絡(luò)通常用G=(V,E)圖來模擬。此時(shí)，網(wǎng)絡(luò)的可靠性可以用圖的邊連通度和連通度來度量。為了更精確的度量互連網(wǎng)絡(luò)的可靠性，人們提出了兩種新的參數(shù)——限制邊連通度和限制連通度。不含三角形的圖，被稱作無三角圖。無三角圖在互連網(wǎng)絡(luò)設(shè)計(jì)方面有著廣泛的應(yīng)用。本項(xiàng)目研究了無三角圖的限制邊連通度的優(yōu)化問題，證明了無三角圖是超級(jí)-λ′的度和條件。

在文中，Shang等[7]證明了超級(jí)-λ′無三角圖的一個(gè)充分條件。

本文證明了G是超級(jí)-λ′的一個(gè)度和條件，改進(jìn)了定理1的結(jié)果。

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

本文證明了超級(jí)-λ′無三角圖的一個(gè)度和條件，該結(jié)論是對(duì)文獻(xiàn)[7]結(jié)果的推廣。下面先給出與其相關(guān)的引理。

引理1[8]設(shè)G是一個(gè)階n≥4的連通無三角圖，若對(duì)任意滿足dist(u,v)=2的點(diǎn)對(duì)u,v∈V(G),有:

與λk(G)≤ξk(G)的假設(shè)矛盾，證明完畢。

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

定理2設(shè)G是一個(gè)階n≥4的連通無三角圖。若對(duì)任意滿足dist(u,v)=2的點(diǎn)對(duì)u,v∈V(G),有:

證明：由引理1知G是λ′-最優(yōu)的，因此λ′(G)=ξ(G).

ξG(uv)=min{ξG(e)∶e∈E(G[U])}

(1)

因?yàn)镚是無三角圖，所以有Ii(u)∩Ij(v)=φ,i,j∈{1,2}.下面分兩種情況進(jìn)行討論。

情形1：I2(u)=φ且I2(v)=φ.

由Ii(u)∩Ij(v)=φ和Ii(u)∪Ij(v)?U{u,v} 可以推出:

與引理2矛盾。

情形2：I2(u)和I2(v)至少有一個(gè)是空集。

不失一般性，假設(shè)I2(u)≠φ.令w是I2(u)中任意的一個(gè)點(diǎn)。 由式(1)，有:

且

(2)

(3)

從而有:

(4)

(5)

結(jié)合上式和式(3)~式(5)及I1(v)的定義，可推出:

與引理2矛盾。

由定理2，直接有以下推論。

推論1設(shè)G是一個(gè)階n≥4的連通二部圖，若對(duì)滿足dist(u,v)=2的點(diǎn)對(duì)u,v∈V(G),有:

圖1　不滿足定理1度和條件的非超級(jí)- λ′圖

則G是超級(jí)-λ′的。

參考文獻(xiàn)：

[1]BALBUENA C，CARMONA A，F(xiàn)ABREGA J，et al.Super connectivity of bipartite digraphs and graphs[J].Discrete Mathematics，1999，197-198：61-75.

[2]BALBUENA C，GARCIA-VAZQEZ P，MARCOTE X.Sufficient conditions forλ′-optimality in graphs with girth g[J].Graph Theory，2006，52：73-86.

[3]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.

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

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

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

[7]SHANG L，ZHANG H P.Sufficient conditions for graphs to beλ′-optimal and super -λ′[J].Networks，2007，49 (3)：234-242.

[8]YUAN J，LIU A X.Sufficient conditions forλk-optimality in triangle-free graphs[J].Discrete Mathematics，2009，310：981-987.

Degree and Sum Conditions for Triangle-free Graphs to be

Super Restricted Edge-connected

YUAN Jun，LIU Ai-Xia

(School of Applied Sciences，Taiyuan University of Science and Technology，Taiyuan 030024，China)

Abstract：An edge cut S of a connected graph G is called as a restricted edge cut if G-S contains no isolated vertices.A graph is to be super restricted edge-connected for short super -λ′,if every minimum restricted edge cut isolates an edge.In this paper，we study the degree sum conditions for triangle-free graphs to be super restricted edge connectivity，and prove that：Let G be a connected triangle-free graph of order.If d(u)+d(v)≥2+3 for each pair vertices u,v∈V(G) with dist(u,v)=2,then G is super -λ′.Moreover， the result is demonstrated to be the best possible.

Key words：restricted edge connectivity，super -λ′ graph,triangle-free graph