Fault-tolerant strong Menger (edge) connectivity and 3-extra edge-connectivity of balanced hypercubes

摘要

A connected graph G is called strongly Menger (edge) connected if for any two distinct vertices x, y of G, there are min{deg(G)(x), deg(G)(y)}(-edge)-disjoint paths between x and y. The g(g 0)-extra edge-connectivity of the connected graph G, denoted by lambda(g)(G), is the minimal cardinality of a set of edges of G, if exists, whose deletion disconnects G and each remaining component contains more than g vertices. In this paper, we show that the n-dimensional balanced hypercube BHn, which is a variant of hypercube Q(n), is still strongly Menger (edge) connected even when there are (2n - 4) faulty vertices (resp. (2n - 2) faulty edges) for n = 2. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that BHn is still strongly Menger edge connected even when there are (6n - 8) faulty edges for n = 2. These results are all optimal with respect to the maximum number of tolerated (edge) faults. Furthermore, we showed that the 3-extra edge-connectivity of B H-n is 8n - 8 for n = 2. (C) 2017 Elsevier B.V. All rights reserved.