The Conditional-( g,d,k )-Connectivity and Conditional-( g,d,k )-edge-Connectivity on the Hypercubes *

Abstract

We propose two new measures of conditional connectivity to be the extension of R_g-connectivity and R_g-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) deg_G–F(p) + deg_G–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κ^g,d,k(λ^g,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ^1,1,k, κ^1,d,2, λ^1,1,1 and λ^1,d,2 for the hypercubes.