Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419437 | Discrete Applied Mathematics | 2012 | 8 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
C. Balbuena, P. García-Vázquez, A. Hansberg, L.P. Montejano,