Conditional Connectivity Measures For Hypercube And Folded Hypercube

Using the graph to study the topology of the network has been widely accepted andapplied by computer scientists, The concept of (edge)connectivity in graph theory is animportant measure for networks, which can correctly re-ects the fault tolerance of systemswith few processor, but it always underestimates the the resilience of large networks.With the development of multiprocessor systems, it is necessary to improve the conceptof traditional connectivity. Motivated by the shortcomings of the traditional connectivity,Harary [17] introduced the concept of conditional connectivity.Let G be a connected undirected graph, and P be a graph-theoretic property, Harary[17] defined the conditional (edge)connectivityκ(G;P)(λ(G;P) as the minimum cardi-nality of a set of vertices(edges), if any, whose deletion disconnects G and every remainingcomponent has property P. Let g be a non-negative integer, and P_g be the property ofhaving at least g vertices. Fa`brega and Fiol [14] defined the g - extra(edge)connectivityκ_g(G)(λ_g(G)) asκ(G;P_g)(λ(G;P_g). That is, the g - extra(edge)connectivity of G is theminimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnectsG, and every remaining component has at least g vertices. Similarly, Let g be a non-negative integer, P_g be the property of having at last g neighbors for any vertex, Latifiin [25] calledκ(G;Pg)(λ(G;Pg) R_g - (edge)connectivity, writtenκg(G)(λg(G)). That is,R_g - (edge)connectivity of G is the minimum cardinality of a set of (edges)vertices ofG, if any, whose deletion disconnects G, and every remaining component has minimumdegree at least g. In this paper, we study above two kinds of conditional connectivity,and determineκ_g(Q_n) for 0≤g≤2n and n≥4;κ_g(FQ_n) for 0≤g≤n - 4 andn≥8, where Qn and FQn denote the n-dimensional hypercube and folded hypercuberespectively. Moreover, we also determine R_g-connectivity of Q_n and characterize theminimal cutsets.