Paired 2-disjoint path covers of faulty k-ary n-cubes

A paired k-disjoint path cover of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. The k-ary n-cube Q n k is one of the most popular interconnection networks. In this paper, we consider the problem of paired 2-disjoint path covers of the k-ary n-cube Q n k (odd k 5 ) with faulty elements (vertices and/or edges) and obtain the following result. Let F be a set of faulty elements in Q n k (odd k 5 ) with | F | 2 n - 4, and { a, b } and { c, d } be its any two pairs of non-faulty vertices. Then the graph Q n k - F contains vertex-disjoint a - b path and c - d path that cover its all non-faulty vertices, and the upper bound 2 n - 4 of faults tolerated is nearly optimal. We also show that Cartesian product Q n k P with at most 2 n - 2 faulty elements is Hamiltonian connected, where P is a path, n 2 and odd k 5 . A paired k-DPC of a graph is a set of k disjoint paths joining k source-sink pairs that cover all vertices of the graph.Let Q n k be the k-ary n-cube and F be a set of faulty elements, where odd k 5 and | F | 2 n - 4 .Let { a, b } and { c, d } be any two pairs of non-faulty vertices. Then Q n k - F has a 2-DPC: a - b path and c - d path.The upper bound 2 n - 4 of faults tolerated is nearly optimal.