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\ge 1$ cycles, each of length at least four and let $h$ be an integer such that $0\le h\le 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)a_h^r$, where $a_h^r$ is the number of vertices of a smallest $h$-regular subgraph of $G.$