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

摘要

We propose two new measures of conditional connectivity to be the extension of Rg -connectivity and Rg -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) degG–F (p ) + degG–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.