Article ID Journal Published Year Pages File Type
419437 Discrete Applied Mathematics 2012 8 Pages PDF
Abstract

For a strongly connected digraph DD the restricted arc-connectivity λ′(D)λ′(D) is defined as the minimum cardinality of an arc-cut over all arc-cuts SS satisfying that D−SD−S has a non-trivial strong component D1D1 such that D−V(D1)D−V(D1) contains an arc. In this paper we prove that a generalized pp-cycle is λ′λ′-optimal if diam(D)≤2ℓ+p−2, where ℓℓ is the semigirth of DD and p≥3p≥3. Further we show that the kk-iterated line digraph is λ′λ′-optimal if diam(D)≤2ℓ+p−2+k for p≥3p≥3. We improve these results for pp large enough and we also improve known results on super-λλ for pp-cycles with p≥3p≥3.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,