Disjoint path covers in recursive circulants G(2m,4) with faulty elements

A k-disjoint path cover of a graph is defined as a set of k 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 k-disjoint path cover of recursive circulant G(2m,4) under the condition that at most f faulty vertices and/or edges are removed. It is shown that when m≥3, G(2m,4) has a k-disjoint path cover (of one-to-one type) joining any pair of two distinct source and sink for arbitrary f and k≥2 subject to f+k≤m. In addition, it is proven that when m≥5, G(2m,4) has a k-disjoint path cover (of unpaired many-to-many type) joining any two disjoint sets of k sources and k sinks for arbitrary f and k≥2 satisfying f+k≤m−1, in which sources and sinks are freely matched. In particular, the mentioned bounds f+k≤m and f+k≤m−1 of the two cases are shown to be optimal.