限制弧连通有向图的充分条件

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件.

Sufficient Conditions for Restricted Arc-Connected Digraphs

Interconnection networks are often modeled by graphs or digraphs.The restrictedarc-connectiVity of digraphs are important measurements for fault tolerance of networks.Let D be a strongly connected digraph.An arc subset S of D is a restricted arc-cut of D if D-S has a non-trivial strong component D1 such that D-V（D1）contains an arc.The restricted arc-connectivity λ′（D）is the minimum cardinality over all restricted arc-cuts of D.A strongly connected digraph D is called λ′-connected,if λ′（D）exists.Let D be a digraph witll finittj girth g·If Cg=u1u2…ugu1 is a g-cycle,then let ξ（Cg）=min{（sum from i=1 to g）d＋（ui）-g}and ξ（D）=min{ξ（Cg）：Cg is a g-cycle}In this paper,we give a sumcient condition for λ′-connected digraphs D with λ′（D）≤ξ（D）.