Local-connectivity on FQn with a large number of faulty nodes

摘要

The n-dimensional folded hypercube FQn is an important variance of the hypercube Qn. It has many attractive properties and has received many researchers' extensive attention. In this paper, we discuss two kinds of local-connectivity based on the folded hypercube network FQ„: local k-sub-folded-hypercube-connectivity and local sub-folded-hypercube-connectivity. Each k-sub-folded-hypercube FQk contains less than 2k−1 faulty nodes in a local k-sub-folded-hypercube-connectivity FQ„, and all the non-faulty nodes in FQk make a connected graph. For each k-sub-folded-hypercube FQk of FQn, where k ≥ 1, there is an h-dimensional sub-folded-hypercube FQh containing FQk(thus h ≥ k) such that FQh is local h-sub-folded-hypercube connected in a local sub-folded-hypercube-connectivity FQ„. We lead two theorems by the definition of local connectivity and show that a locally connected FQn with a large number of faulty nodes is also globally connected. By the results of this paper, the fault tolerant capability of FQn is improved greatly.