The vulnerability of the diameter of the enhanced hypercubes

Publication date 12 September 2017

Abstract: For an interconnection network

G

, the {it

o m e g a

-wide diameter}

d_{o} m e g a (G)

is the least

e l l

such that any two vertices are joined by

o m e g a

internally-disjoint paths of length at most

e l l

, and the {it

(o m e g a - 1)

-fault diameter}

D_{o m e g a} (G)

is the maximum diameter of a subgraph obtained by deleting fewer than

o m e g a

vertices of

G

. The enhanced hypercube

Q_{n, k}

is a variant of the well-known hypercube. Yang, Chang, Pai, and Chan gave an upper bound for

d_{n + 1} (Q_{n, k})

and

D_{n + 1} (Q_{n, k})

and posed the problem of finding the wide diameters and fault diameters of

Q_{n, k}

. By constructing internally disjoint paths between any two vertices in the enhanced hypercube, for

n g e 3

and

2 l e k l e n

we prove

D_omega(Q_{n,k})=d_omega(Q_{n,k})=�egin{cases} d(Q_{n,k}) & extrm{for

1 l e q o m e g a < n - l f l o o r f r a c k 2 f l o o r

;}\ d(Q_{n,k})+1 & extrm{for

n - l f l o o r f r a c k 2 f l o o r l e q o m e g a l e q n + 1

.} end{cases}

where

d (Q_{n, k})

is the diameter of

Q_{n, k}

. These results mean that interconnection networks modelled by enhanced hypercubes are extremely robust.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: The vulnerability of the diameter of the enhanced hypercubes