超級-λ’無三角圖的度和充分條件

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

原軍， 劉愛霞

(太原科技大學應用科學學院，太原 030024)

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

關鍵詞：限制邊連通度；超級-λ′圖；無三角圖

收稿日期：2015-03-11

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

作者簡介：原軍(1979-)，男，副教授，主要研究方向為圖論及其應用。

中圖分類號：O157.5文獻標志碼：A

1預備知識

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

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

本文證明了G是超級-λ′的一個度和條件，改進了定理1的結果。

2主要結果及其證明

本文證明了超級-λ′無三角圖的一個度和條件，該結論是對文獻[7]結果的推廣。下面先給出與其相關的引理。

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

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

下面給出主要的結論及其證明。

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

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

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

(1)

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

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

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

與引理2矛盾。

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

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

且

(2)

(3)

從而有:

(4)

(5)

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

與引理2矛盾。

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

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

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

則G是超級-λ′的。

參考文獻：

[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