The vulnerability of the diameter of folded n-cubes

✍ Scribed by E. Simó; J.L.A. Yebra

• Book ID: 104114026
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 247 KB
• Volume: 174
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)80334-2

✦ Synopsis

Fault tolerance concern in the design of interconnection networks has arisen interest in the study of graphs such that the subgraphs obtained by deleting some vertices or edges have a moderate increment of the diameter. Besides the general problem, several particular families of graphs are worthy of consideration. Both the odd graphs and the n-cubes have been studied in this context. In this paper we deal with folded n-cubes, a much interesting family because: (i) like the n-cubes, their order is a power of 2, (ii) their diameter is half the diameter of the n-cube of the same order, while their degree only increases by one, and (iii) as we show, in a folded n-cube of degree A, the deletion of less than [½AJ -1 vertices or edges does not increase the diameter of the graph, and the deletion of up to d -1 vertices or edges increases it by at most one. This last property means that interconnection networks modelled by folded n-cubes are extremely robust.