Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333882 | Theoretical Computer Science | 2016 | 6 Pages |
Abstract
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 Qnk 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 Qnk (odd kâ¥5) with faulty elements (vertices and/or edges) and obtain the following result. Let F be a set of faulty elements in Qnk (odd kâ¥5) with |F|â¤2nâ4, and {a,b} and {c,d} be its any two pairs of non-faulty vertices. Then the graph QnkâF contains vertex-disjoint aâb path and câd path that cover its all non-faulty vertices, and the upper bound 2nâ4 of faults tolerated is nearly optimal. We also show that Cartesian product QnkÃP with at most 2nâ2 faulty elements is Hamiltonian connected, where P is a path, nâ¥2 and odd kâ¥5.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xie-Bin Chen,