The vulnerability of the diameter of folded \(n\)-cubes (Q1377783): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Sergei L. Bezrukov / rank | |||
Property / reviewed by | |||
Property / reviewed by: Sergei L. Bezrukov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3039368 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4770409 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3686639 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3992965 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A study of odd graphs as fault-tolerant interconnection networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fault diameter of interconnection networks / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(97)80334-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2079309736 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:24, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The vulnerability of the diameter of folded \(n\)-cubes |
scientific article |
Statements
The vulnerability of the diameter of folded \(n\)-cubes (English)
0 references
19 July 1998
0 references
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.
0 references
fault-tolerance
0 references
diameter
0 references
folded cubes
0 references