Abstract: A network is often modeled by a graph G=(V,E) with the vertices representing nodes such as processors or stations, and the edges representing links between the nodes. One fundamental consideration in the design of networks is reliability. Let G be a connected graph and P be graph-theoretic property. The conditional connectivity λ(G,P) or κ(G,P) is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects G and each remaining component has property P. Let F be a vertex set or edge set of G and P be the property of G-F with at least r components. Then we have r-component connectivity cκr(G) and the r-component edge connectivity cλr(G). In this paper, we determine the r -component edge connectivity of hypercubes and folded hypercubes.

Keywords: Reliability, Conditional connectivity, Cut, Networks, Component, Graph

Pages: 331-338