Asymptotic reliability of the hypercube and the d-octahedral networks.

摘要

his dissertation investigates the asymptotic reliability of the hypercube and the d-octahedral networks. The hypercube network, also known as the boolean or binary d-cube, is a regular undirected graph with 2;The d-octahedral network is a regular undirected graph with 2d vertices and (2d - 2)d edges. It is also known as the complete d-partite graph K;The vertices in the hypercube or in the d-octahedral network are assumed to be perfectly reliable, whereas each edge is successfully operational with probability p, ;The reliability of the hypercube or the d-octahedral network, with edge-reliability p, is the probability that, given any two vertices in the network, there exists a path of only operational edges connecting them. The asymptotic reliability of the hypercube or the d-octahedral network is the limit (if it exists) of the reliability of the network as its dimension approaches infinity.;Although there have been many papers over the years that have addressed the reliability of the hypercube network, little is known about its asymptotic reliability. The d-octahedron is studied in graph theory, but it has not been used as a topological structure that can be viewed as an interconnection network.;This dissertation shows that the asymptotic reliability of the hypercube network, with edge-reliability p, is 0 for