关键词: 互连网络, 限制边割, 限制边连通度, 极大限制边连通图

Abstract: The restricted edge connectivity is an important index to measure the reliability of networks. For a connected network [G] with edge set [E], an edge set [S?E] is a restricted edge cut if [G-S] is disconnected and every component of [G-S] has at least two vertices. The restricted edge connectivity of [G], denoted by[λ'], is defined as the cardinality of a minimum restricted edge cut. Let [d(v)] be the degree of a vertex [v] and let [ξ=min{d(u)+d(v)-2:uv∈E}] be the minimum edge degree of [G]. A connected network [G] is maximally restricted edge-connected if[λ'=ξ]. In this paper, some sufficient conditions are presented for networks to be maximally restricted edge-connected.

Key words: interconnection networks, restricted edge cuts, restricted edge connectivity, maximally restricted edge-connected graphs