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 g e q 1

cycles, each of length at least four and let

h

be an integer such that

0 l e q h l e q 2 r - 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

(2 r - h) a_{h}^{r}

, where

a_{h}^{r}

is the number of vertices of a smallest

h

-regular subgraph of

G .

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On conditional connectivity of the Cartesian product of cycles