The vulnerability of the diameter of folded \(n\)-cubes
type: Item
instance of: scholarly article
title: The vulnerability of the diameter of folded \(n\)-cubes
zbMATH Open document ID: 0892.05024
DOI: 10.1016/S0012-365X(97)80334-2
author: J. Ning
published in: Discrete Mathematics
publication date: 1998-07-19T00:00:00Z
review text: The paper deals with the fault-tolerance properties of the folded \(n\)-cube, which is defined as the graph obtained from the \(n\)-dimensional unit cube by identifying its opposite vertices. The question is how many vertices (resp. edges) can one delete so that the diameter of the remaining graph is close to the original one. The authors show that between any two vertices of the folded \(n\)-cube there exist \(n\) vertex disjoint paths of length at most \(\lfloor n/2\rfloor +1\). This implies that if \(s\) vertices of the folded \(n\)-cube are deleted then the diameter of the remaining graph is not changed if \(0\leq s < \lfloor (n-2)/2\rfloor\), and, respectively increases on 1 if \(\lfloor (n-2)/2\rfloor \leq s\leq n-1\). Since the paths in the proposition above are vertex-disjoint, a similar result also holds for the deletion of \(s\) edges.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1110043
zbMATH Keywords: fault-tolerance
zbMATH Keywords: diameter
zbMATH Keywords: folded cubes
reviewed by: Sergej L. Bezrukov
MaRDI profile type: Publication
cites work: Q3039368
cites work: Q4770409
cites work: Q3686639
cites work: Q3992965
cites work: A study of odd graphs as fault-tolerant interconnection networks
cites work: Fault diameter of interconnection networks
full work available at URL: s0012-365x(97)80334-2
OpenAlex ID: W2079309736
description: scientific article; zbMATH DE number 1110043