The Edge Connectivity of Expanded -Ary -Cubes

Mass data processing and complex problem solving have higher and higher demands for performance of multiprocessor systems. Many multiprocessor systems have interconnection networks as underlying topologies. The interconnection network determines the performance of a multiprocessor system. The network is usually represented by a graph where nodes (vertices) represent processors and links (edges) represent communication links between processors. For the network , two vertices and of are said to be connected if there is a -path in . If has exactly one component, then is connected; otherwise is disconnected. In the system where the processors and their communication links to each other are likely to fail, it is important to consider the fault tolerance of the network. For a connected network , its inverse problem is that is disconnected, where or . The connectivity or edge connectivity is the minimum number of . Connectivity plays an important role in measuring the fault tolerance of the network. As a topology structure of interconnection networks, the expanded -ary -cube has many good properties. In this paper, we prove that (1) is super edge-connected ( ); (2) the restricted edge connectivity of is ( ); (3) is super restricted edge-connected ( ).