The star-structure connectivity and star-substructure connectivity of hypercubes and folded hypercubes

Publication date: 28 September 2020

Abstract: As a generalization of vertex connectivity, for connected graphs

G

and

T

, the

T

-structure connectivity

k a p p a (G, T)

(resp.

T

-substructure connectivity

k a p p a^{s} (G, T)

) of

G

is the minimum cardinality of a set of subgraphs

F

of

G

that each is isomorphic to

T

(resp. to a connected subgraph of

T

) so that

G - F

is disconnected. For

n

-dimensional hypercube

Q_{n}

, Lin et al. [6] showed

k a p p a (Q_{n}, K_{1, 1}) = k a p p a^{s} (Q_{n}, K_{1, 1}) = n - 1

and

k a p p a (Q_{n}, K_{1, r}) = k a p p a^{s} (Q_{n}, K_{1, r}) = l c e i l f r a c n 2 c e i l

for

2 l e q r l e q 3

and

n g e q 3

. Sabir et al. [11] obtained that

k a p p a (Q_{n}, K_{1, 4}) = k a p p a^{s} (Q_{n}, K_{1, 4}) = l c e i l f r a c n 2 c e i l

for

n g e q 6

, and for

n

-dimensional folded hypercube

F Q_{n}

,

k a p p a (F Q_{n}, K_{1, 1}) = k a p p a^{s} (F Q_{n}, K_{1, 1}) = n

,

k a p p a (F Q_{n}, K_{1, r}) = k a p p a^{s} (F Q_{n}, K_{1, r}) = l c e i l f r a c n + 1 2 c e i l

with

2 l e q r l e q 3

and

n g e q 7

. They proposed an open problem of determining

K_{1, r}

-structure connectivity of

Q_{n}

and

F Q_{n}

for general

r

. In this paper, we obtain that for each integer

r g e q 2

,

k a p p a (Q_{n}; K_{1, r}) = k a p p a^{s} (Q_{n}; K_{1, r}) = l c e i l f r a c n 2 c e i l

and

k a p p a (F Q_{n}; K_{1, r}) = k a p p a^{s} (F Q_{n}; K_{1, r}) = l c e i l f r a c n + 1 2 c e i l

for all integers

n

larger than

r

in quare scale. For

4 l e q r l e q 6

, we separately confirm the above result holds for

Q_{n}

in the remaining cases.

This page was built for publication: The star-structure connectivity and star-substructure connectivity of hypercubes and folded hypercubes