The reliability of lexicographic product digraphs

摘要

For two digraphs D = (V-1 , A(1)) and H = (V-2, A(2)), the lexicographic product digraph D[H] is the digraph with vertex set V-1 x V-2. There is an arc from vertex (x(1), y(1)) to vertex (x(2), y(2)) in D[H] if and only if either x(1) x(2) is an element of A(1) or x(1) = x(2) and y(1)y(2) is an element of A(2). The minimum degree and the arc-connectivity of D are denoted by delta(D) and lambda(D), respectively. We prove that for any two digraphs D and H, lambda(D[H]) >= min{n(t + lambda(D) - delta(D) - 1) + delta(D[H]), n(2)lambda(D)} holds for any t <= min{delta (D) - lambda(D) +1, lambda(D) + 1, n - 1}, where n = vertical bar V (H)vertical bar. As a consequence, lambda(D[H]) >= n(lambda(D) - delta(D)) + delta(D[H]). We also provide some sufficient conditions for D[H] to have maximum reliability with respected the connectedness and super connectedness. (C) 2019 Elsevier Inc. All rights reserved.