Component Connectivity Of The Hypercube And The Folded Hypercube

The topology of a network usually modelled by a connected graph,where the proces-sors are represented by vertices and the links are represented by edges.The concepts of connectivity and edge connectivity are two important parameters to evaluate the reliability of a network.But with the development of multiprocessor systems,the traditional connec-tivity can not reflect the fault tolerance of a network accurately.Based on the deficiency of the traditional connectivity,Harary gave the definition of conditional(edge)connectivity.The conditional(edge)connectivity is the minimum number of(edges)vertices whose deletion results in a disconnected graph and every component has the property P.In 1984,Chartrand and Sampathkumar introduced the concepts of component connectiv-ity and component edge connectivity respectively.They can be regarded a kind of conditional connectivity,and they are the generalization of the traditional connectivity essentially.For a non-complete graph,the g-component(edge)connectivity(c?g(G))ckg(G)is the minimum number of(edges)vertices whose deletion results in a graph with at least g components.And(e?2(G))ck2(G)is the traditional(edge)connectivity.In this paper,we mainly study the component connectivity and component edge connectivity of the hypercube and the folded hypercube respectively.