Strong Menger connectedness of augmented k-ary n-cubes

Abstract: A connected graph

G

is called strongly Menger (edge) connected if for any two distinct vertices

x, y

of

G

, there are

m i n {m d e g}_{G} (x), {m d e g}_{G} (y)

vertex(edge)-disjoint paths between

x

and

y

. In this paper, we consider strong Menger (edge) connectedness of the augmented

k

-ary

n

-cube

A Q_{n, k}

, which is a variant of

k

-ary

n

-cube

Q_{n}^{k}

. By exploring the topological proprieties of

A Q_{n, k}

, we show that

A Q_{n, 3}

for

n g e q 4

(resp.

A Q_{n, k}

for

n g e q 2

and

k g e q 4

) is still strongly Menger connected even when there are

4 n - 9

(resp.

4 n - 8

) faulty vertices and

A Q_{n, k}

is still strongly Menger edge connected even when there are

4 n - 4

faulty edges for

n g e q 2

and

k g e q 3

. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that

A Q_{n, k}

is still strongly Menger edge connected even when there are

8 n - 10

faulty edges for

n g e q 2

and

k g e q 3

. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.

This page was built for publication: Strong Menger connectedness of augmented $k$-ary $n$-cubes