On Conditional Connectivity of the Cartesian Product of Cycles

Abstract

The conditional h-vertex (h-edge) connectivity of a connected graph H of minimum degree k > h is the size of a smallest vertex (edge) set F of H such that H − F is a disconnected graph of minimum degree at least h. Let G be the Cartesian product of r ≥ 1 cycles, each of length at least four and let h be an integer such that 0 ≤ h ≤ 2r − 2. In this paper, we determine the conditional h-vertex-connectivity and the conditional h-edge-connectivity of the graph G. We prove that both these connectivities are equal to (2r−h)arh, where arh is the number of vertices of a smallest h-regular subgraph of G.

Keywords

• fault tolerance
• hypercube
• conditional connectivity
• cut
• cartesian product
• 05c40
• 68r10