The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks.This paper determines that the h-restricted arc-connectivity of the Harary digraph D=G(n;...The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks.This paper determines that the h-restricted arc-connectivity of the Harary digraph D=G(n;1,2,.:,k)is equal to n/2 for 2≤h≤n/2,k=2 and n iseven,andλ_(h)(D)=g(k-1)for 2<h≤g and 3≤k≤n/2,where g is the girth of D.As consequences,the super restricted arc-connectedness of Harary digraph D is obtained immediately.In particular,for k=2 and n is even or 3≤k<n/2and n can be divided by k,it can be determined that distinct positive(respectively,negative)Ah-superatoms of D are vertex disjoint for 2≤h≤g.展开更多
For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′（D） is defined as the S satisfying that D - S has a non-trivial strong component D1 such th...For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′（D） is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V（D1） contains an arc. Let S be a subset of vertices of D. We denote by w＋（S） the set of arcs uv with u ∈ S and v S, and by w-（S） the set of arcs uv with u S and v ∈ S. A digraph D = （V, A） is said to be λ′-optimal if λ′（D） =ξ′（D）, where ξ′（D） is the minimum arc-degree of D defined as ξ（D） = min {ξ′（xy） ： xy ∈ A}, and ξ′（xy） = min（｜ω＋（{x,y}）｜, ｜w-（{x,y}）｜, ｜w＋（x） ∪ w- （y） ｜, ｜w- （x） ∪ω＋ （y）｜}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh（D） of a s-geodetic digraph is λ′-optimal for certain iteration h.展开更多
基金the National Natural Science Foundation of China(No.11531011).
文摘The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks.This paper determines that the h-restricted arc-connectivity of the Harary digraph D=G(n;1,2,.:,k)is equal to n/2 for 2≤h≤n/2,k=2 and n iseven,andλ_(h)(D)=g(k-1)for 2<h≤g and 3≤k≤n/2,where g is the girth of D.As consequences,the super restricted arc-connectedness of Harary digraph D is obtained immediately.In particular,for k=2 and n is even or 3≤k<n/2and n can be divided by k,it can be determined that distinct positive(respectively,negative)Ah-superatoms of D are vertex disjoint for 2≤h≤g.
基金Supported by the Ministry of Education and Science, Spainthe European Regional Development Fund (ERDF) under project MTM2008-06620-C03-02the Andalusian Government under project P06-FQM-01649
文摘For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′（D） is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V（D1） contains an arc. Let S be a subset of vertices of D. We denote by w＋（S） the set of arcs uv with u ∈ S and v S, and by w-（S） the set of arcs uv with u S and v ∈ S. A digraph D = （V, A） is said to be λ′-optimal if λ′（D） =ξ′（D）, where ξ′（D） is the minimum arc-degree of D defined as ξ（D） = min {ξ′（xy） ： xy ∈ A}, and ξ′（xy） = min（｜ω＋（{x,y}）｜, ｜w-（{x,y}）｜, ｜w＋（x） ∪ w- （y） ｜, ｜w- （x） ∪ω＋ （y）｜}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh（D） of a s-geodetic digraph is λ′-optimal for certain iteration h.
