Litao Guo



Fault Tolerance of Hypercubes and Folded Hypercubes

pdf PDF


Interconnection networks; Fault tolerance; r-component edge connectivity


Connectivity is a vital metric to explore fault tolerance and reliability of network structure based on a graph model. There are many kinds of connectivity to measure the fault tolerance and reliability of networks, such as classic connectivity, super connectivity, extraconnectivity. In this paper we focus on the number of components of graph which is called component connectivity. Let G = (V, E) be a connected graph. A r-component cut of G is a set of vertices whose deletion results in a graph with at least r components. r-component connectivity cκr (G) of G is the size of the smallest r-component cut. The r-component edge connectivity cλr (G) can be defined similarly. In this paper, we determine the r-component edge connectivity of hypercubes and folded hypercubes:(1) cλ2(Qn) = λ(Qn) = n for n ≥ 2. (2) cλ3(Qn) = 2n − 1 for n ≥ 2. (3) cλ4(Qn) = 3n − 2 for n ≥ 2. (4) cλ2(F Qn) = n + 1 for n ≥ 3. (5) cλ3(F Qn) = 2n + 1 for n ≥ 3. (6) cλ4(F Qn) = 3n + 1 for n ≥ 3.

Cite this paper

Litao Guo. (2017) Fault Tolerance of Hypercubes and Folded Hypercubes. International Journal of Mathematical and Computational Methods, 2, 72-75