| This dissertation considers the fault tolerance of interconnection networks and the problem embedding paths into fault-tolerant networks. It is well-known that when the underlying topology of an interconnection network is modeled by a connected graph G= (V, E), where V is the set of elements and E is the set of communication links in the network, the vertex-connectivityκ(G) and edge-connectivityλ(G) are important measurements for fault tolerance of the network. This implies that the network can tolerateκ(G)-1 element failures orλ(G)-1 link failures to remain connected. Thus, the higher the vertex-connectivity or the edge-connectivity is, the more reliable the network is.At the present time, the n-dimensional cube or the hypercube, denoted by Qn, is one of the most popular, versatile and efficient topological structures of interconnection networks. The hypercube has many excellent features, and, thus becomes the first choice for the topological structure of parallel processing and computing systems. It has been proved that the vertex-connectivity and the edge-connectivity of Qn are both n.To measure fault tolerance of networks well and truly, more refined indices than vertex-connectivity and edge-connectivity, super vertex-connectivity and super edge-connectivity were proposed. The super vertex-connectivityκs(G) (resp. super edge-connectivityλs(G)) of a connected graph G is the minimum number of vertices (resp. edges) whose removal results in a disconnected graph and contains no isolated vertices.In 1989, Esfahanian showedκs(Qn)=λs(Qn)= 2n-2 for the n-dimensional cube Qn, which implies that if 2n- 3 vertices or edges fail at the same time in Qn and each vertex is incident with at least one fault-free edge, then there exists a fault-free uv-path in Qn for any two distinct fault-free vertices u and v in Qn. On the one hand, in 2003, Xu et al showed that when Qn has at most 2n-3 faulty edges and each vertex is incident with at least one fault-free edge, there exists a fault-free uv-path of length at most d+4 in Qn for any two distinct vertices u and v in Qn, where d is the distance between u and v in Qn,2≤d≤n- 2 and n≥4. On the other hand, in 1991, Chan and Lee showed that there is a Qn with 2n- 4 faulty edges and each vertex is incident with at least two fault-free edges, and it contains no fault-free Hamilton cycles, which shows that for a fault-free edge uv, Qn contains no fault-free uv-path of length 2n-1. In this dissertation, we show that for any two distinct vertices u and v with distance d in the hypercube Qn (n≥3) with at most 2n-5 faulty edges and each vertex is incident with at least two fault-free edges, there exists a fault-free uv-path of length l in Qn for every l with d+4≤l≤2n-1 and l-d= 0 (mod 2). This result improves some known results on edge-fault pancyclity and panconnectivity of hypercubes.The other part of this dissertation considers the fault tolerance of the n-dimensional varietal hypercube VQn and the permutation graph (G0, G1;M), which are a variation and a generation of the hypercube network, respectively. We show thatκ(VQn)=λ(VQn)= n andκs(VQn) =λs(VQn)= 2n-2. For the permutation graph G= G(G0, G1; M) of twoκ-regularκ-connected graphs G0 and G1, we give a suf-ficient and necessary condition forκs(G)>κ(G) andλs(G)>λ(G), and a sufficient condition forκs(G) = 2k andλs(G) = 2k. As applications, we show that the super vertex-connectivity and the super edge-connectivity of some well-known interconnec-tion networks such as n-dimensional hypercubes, twisted cubes, cross cubes, Mobius cubes, locally twisted cubes and varietal hypercubes are both 2n-2. These results can provide more accurate measurements for reliability and fault tolerance of the system when they are used to model the topological structure of a large-scale parallel process-ing system.
|
PDF Full Text Request