A Kind of Conditional Vertex Connectivity of Recursive Circulants

Abstract

A vertex subset $F$ is an $R_k$-vertex-cut of a connected graph $G$ if $G–F$ is disconnected and every vertex in $G–F$ has at least $k$ neighbors in $G–F$. The cardinality of the minimum $R_k$-vertex-cut of $G$ is the $R_k$-connectivity of $G$, denoted by ${\kappa }^k(G)$. This parameter measures a kind of conditional fault tolerance of networks. In this paper, we determine $R_2$-connectivity and $R_3$-connectivity of recursive circulant graphs $G(2^m,2)$.