The vulnerability of the diameter of the enhanced hypercubes

Concern about fault tolerance in the design of interconnection networks has raised interest in the study of graphs such that deleting some vertices increases the diameter only moderately. For an interconnection network G, the (omega - 1)-fault diameter D-omega(G) is the maximum diameter of a subgraph obtained by deleting fewer than omega vertices of G, and the omega-wide diameter d(omega)(G) is the least l such that any two vertices are joined by omega internally -disjoint paths of length at most l. The enhanced hypercube Q(n,k) is a variant of the well-known n -dimensional hypercube Q(n) in which an edge is added from each vertex x(n), ... , x(1) to the vertex obtained by complementing x(k), ... , x(1). Yang, Chang, Pai, and Chan gave an upper bound for d(n+1)(Q(n,k)) and Dn+1 (Q(n,k)) and posed the problem of finding the wide diameter and fault diameter of Q(n,k). By constructing internally disjoint paths between any two vertices in the enhanced hypercube, for n >= 3 and 2 <= k <= n we prove that D-omega(Q(n,k)) = d(omega)(Q(n,k)) = d(Q(n,k)) for 1 <= omega < n - left perpendiculark/2right perpendicular; D-omega(Q(n,k)) = d(omega)(Q(n,k)) = d(Q(n,k)) + 1 for n - left perpendiculark/2right perpendicular <= omega <= n + 1, where d(Q(n,k)) is the diameter of Q(n,k). These results mean that interconnection networks modeled by enhanced hypercubes are extremely robust. (C) 2017 Elsevier B.V. All rights reserved.