Abstract
In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercubelike networks with n - 2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u), deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n - 5 vertex faults. (C) 2007 Elsevier B.V. All rights reserved.
Original language | English |
---|---|
Pages (from-to) | 64-69 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 106 |
Issue number | 2 |
DOIs | |
State | Published - 15 Apr 2008 |
Keywords
- strong Menger connectivity; conditional faults; hypercube-like network; interconnection networks