Affiliations: [a] College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China | [b] School of Computer Science and Technology, Soochow University, Suzhou 215006, China | [c] Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C. yhteng@pu.edu.tw
Correspondence:
[†]
Address for correspondence: Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.
Note: [*] This paper is an extended version presented at IEEE CSE 2014 Conference.
Abstract: 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.
