超级-λ′无三角图的度和充分条件

原军， 刘爱霞

(太原科技大学应用科学学院，太原 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

基金项目：国家数学天元基金(11126076)；国家青年科学基金(61402317)；山西省青年自然科学基金(2012021001-2)

作者简介：原军(1979-)，男，副教授，主要研究方向为图论及其应用。

中图分类号：O157.5文献标志码：A

1预备知识

互连网络的可靠性是互连网络设计中一个最基本而又重要的研究课题。互连网络通常用G=(V,E)图来模拟。此时，网络的可靠性可以用图的边连通度和连通度来度量。为了更精确的度量互连网络的可靠性，人们提出了两种新的参数——限制边连通度和限制连通度。不含三角形的图，被称作无三角图。无三角图在互连网络设计方面有着广泛的应用。本项目研究了无三角图的限制边连通度的优化问题，证明了无三角图是超级-λ′的度和条件。

在文中，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是λ′-最优的，因此λ′(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，FABREGA 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