Edge fault tolerance analysis of a class of interconnection networks

摘要

Fault tolerant measures have played an important role in the reliability of an interconnection network. Edge connectivity, restricted-edge-connectivity, extra-edge-connectivity and super-edge-connectivity of many well-known interconnection networks have been explored. In this paper, we study the 2-extra-edge connectivity of a special class of graphs G(G0, G1; M) proposed by Chen et al. [Appl. Math. Comput. 140 (2003) 245–254]. Then by showing that several well-known interconnection networks such as hypercubes, twisted cubes, crossed cubes and Möbius cubes are all contained in this class. We show that their 2-extra-edge-connectivity are all not less than 3n − 4 when their dimension n is not less than 4. That is, when n ⩾ 4, at least 3n − 4 edges are to be removed to get any of an n-dimensional above networks disconnected provided that the removed edges does not isolate a vertex or an edge in the faulty networks. Compared with previous results, our result enhances the fault tolerant ability of above networks theoretically.