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

Lun-Min Shih, Chieh-Feng Chiang, Lih Hsing Hsu, Jiann-Mean Tan

Research output: Contribution to journalArticle

26 Scopus citations

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 languageEnglish
Pages (from-to)64-69
Number of pages6
JournalInformation Processing Letters
Volume106
Issue number2
DOIs
StatePublished - 15 Apr 2008

Keywords

  • strong Menger connectivity; conditional faults; hypercube-like network; interconnection networks

Fingerprint Dive into the research topics of 'Strong Menger connectivity with conditional faults on the class of hypercube-like networks'. Together they form a unique fingerprint.

Cite this