Strong Menger connectivity with conditional faults on the class of hypercube-like networks

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.