Paired Many-to-Many Disjoint Path Covers in Recursive Circulants $(G(2^m,4))$

Abstract

A disjoint path cover (DPC for short) of a graph is a set of disjoint paths that cover all the vertices of the graph. A paired many-to-many k-DPC is a DPC composed of k paths between k sources and k sinks, such that each source is joined to a designated sink. We show that recursive circulant G(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> ,4) with at most f faulty vertices and/or edges being removed has a paired many-to-many k-DPC joining k arbitrary sources and sinks for any f and k ≥ 2, subject to f+2k ≤ m+1, where m ≥ 5. The bound m+1 on f+2k is the best possible.