The vulnerability of the diameter of folded \(n\)-cubes (Q1377783): Difference between revisions

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.