Subgraph fault tolerance of distance optimally edge connected hypercubes and folded hypercubes

摘要

Hypercube and folded hypercube are the most fundamental interconnection networks for the attractive topological properties. We assume for any distinct vertices u, v ∈ V, k(u, v) defined as local connectivity of u and v, is the maximum number of independent (u, v)-paths in G. Similarly, λ(u, v) is local edge connectivity of u. v. For some t ∈ [1. D(G)]. (A) u. v ∈ V.u ≠ v, and d(u, v) = t, if k(u, v)(or λ(u, v)) = min{d(u), d(v)}, then G is t-distance optimally (edge) connected, where D(G) is the diameter of G and d(u) is the degree of u. For all integers 0 ＜ k ≤ t, if G is /(-distance optimally connected, then we call G is t-distance local optimally connected. Similarly, we have the definition of t-distance local optimally edge connected. In this paper, we show that after deleting Q_k(k ≤ n - 1), Q_n - Q_k and FQ_n - Q_k are 2-distance local optimally edge connected.