Edge-fault tolerance of hypercube-like networks
This paper considers a kind of generalized measure lambda((h))(s) of fault tolerance in a hypercube-like graph G(n) which contains several well-known interconnection networks such as hypercubes, varietal hypercubes, twisted cubes, crossed cubes, Mobius cubes and the recursive circulant G(2(n), 4), and proves lambda((h))(s) (G(n)) = 2(h) (n - h) for any h with 0 <= h <= n - 1 by the induction on n and a new technique. This result shows that at least 2(h) (n - h) edges of G(n) have to be removed to get a disconnected graph that contains no vertices of degree less than h. Compared with previous results, this result enhances fault-tolerant ability of the above-mentioned networks theoretically. (C) 2013 Elsevier B.V. All rights reserved.
fault tolerance hypercube-like networks combinatorics connectivity super-connectivity