Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875975 | Theoretical Computer Science | 2016 | 20 Pages |
Abstract
For two disjoint vertex-sets, S={s1,â¦,sk} and T={t1,â¦,tk} of a graph, an unpaired many-to-many k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths {P1,â¦,Pk} that altogether cover every vertex of the graph, in which Pi is a path from si to some tj for 1â¤i,jâ¤k. A family of hypercube-like interconnection networks, called restricted hypercube-like graphs, includes most nonbipartite hypercube-like networks found in the literature, such as twisted cubes, crossed cubes, Möbius cubes, recursive circulant G(2m,4) of odd m, etc. In this paper, we show that every m-dimensional restricted hypercube-like graph, mâ¥5, with at most f faulty vertices and/or edges being removed has an unpaired many-to-many k-disjoint path cover joining arbitrary disjoint sets S and T of size k each subject to kâ¥2 and f+kâ¤mâ1. The bound mâ1 on f+k is the maximum possible.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jung-Heum Park,