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)\).