Disjoint path covers in recursive circulants with faulty elements

Abstract: A -disjoint path cover of a graph is defined as a set of internally vertex-disjoint paths connecting given sources and sinks in such a way that every vertex of the graph is covered by a path in the set. In this paper, we analyze the -disjoint path cover of recursive circulant under the condition that at most faulty vertices and/or edges are removed. It is shown that when , has a -disjoint path cover (of one-to-one type) joining any pair of two distinct source and sink for arbitrary and subject to . In addition, it is proven that when , has a -disjoint path cover (of unpaired many-to-many type) joining any two disjoint sets of sources and sinks for arbitrary and satisfying , in which sources and sinks are freely matched. In particular, the mentioned bounds and of the two cases are shown to be optimal. [Copyright &y& Elsevier]