The restricted h-connectivity of balanced hypercubes

Abstract: The restricted

h

-connectivity of a graph

G

, denoted by

k a p p a^{h} (G)

, is defined as the minimum cardinality of a set of vertices

F

in

G

, if exists, whose removal disconnects

G

and the minimum degree of each component of

G - F

is at least

h

. In this paper, we study the restricted

h

-connectivity of the balanced hypercube

B H_{n}

and determine that

k a p p a^{1} (B H_{n}) = k a p p a^{2} (B H_{n}) = 4 n - 4

for

n g e q 2

. We also obtain a sharp upper bound of

k a p p a^{3} (B H_{n})

and

k a p p a^{4} (B H_{n})

of

n

-dimension balanced hypercube for

n g e q 3

(

n e q 4

). In particular, we show that

k a p p a^{3} (B H_{3}) = k a p p a^{4} (B H_{3}) = 12

.

This page was built for publication: The restricted $h$-connectivity of balanced hypercubes