RESTRICTED CUTS IN HYPERCUBES

Kyungpook Mathem.at.ical ^{Joum 허} Vol.34. No.2‘ 229-237‘ December 1994

RESTRICTED CUTS IN HYPERCUBES

A. Duksu Oh

Dedicated to Professor Younki Chae on his sixtieth birthday

For an n-dimensional hypercube Qn and a given integer p (1

<

P ~

n), the minimum cardinality of a p-restricted cut of Qn, denoted K(n,p), provides a generalized measure of node fault tolerance in n-cube networks

,

where a p-restricted cut of Qn is a vertex cut of Qn which contains at most p neighbors of each vertex in Qn. This paper is concerned with K(n,p) and the structure of the minimum cardinality p-restricted cuts of Qn. It is shown that Qn admits a ]>-restricted cut if and only if n

<

3p - 2ι

,

and

“

t^hat K(1’11 ，]>끼) 즈 p2^{n-p 、}w‘v애/

K(I1,p) = ]>2π p

“

^{f and on비1ly if n ~ 3p - 2,’ and n ~ 2p for ]>}

^>

^{3. This}

paper also presents for each )J and n

(1 <

p ~ 11 ~ 3p - 2

,

and n ~ 2)J for

)J

>

3), a characterization of all minimum cardinality p-restricted cuts of

Q

’‘’ and an algorithm for finding all such cuts of Qn.

1.

Introduction and Notation

The notion of connectivity generalization was introduced by F. Harary [1]. [n an application to fault tolerance analysis for a multicomputer whose underlying network topology is modeled by G, the classical vertex connec^• tivity is the minimum cardinality

IFI

^{of a set of faulty} processors F 5uch that G - F is disconnected. However, the processors in such an F may not

[비 1 simultaneously (i.e.

,

F ^l11ay belong \.0 forbidden faulty sets); thus

,

^the

classical vertex connectivity is not an accurat.e deterministic l11easure of node fault tolerance of the network topology for a l11ulticomputer in which some su bsets of the processors do not fail simultaneously. Esfahanian and

Received July 3, 1993

229

230 ^{A. Duksu Oh}

Hakimi [2J proposed, mainly because of the deficiency of the c1assical ver- tex connectivity in the above context, generalized vertex connectivities (by imposing some conditions or restrictions on the components of G - F and/or the set F) as models to analyze the reliability of such networks.

[We note that for a connected graph G the problem of finding the mini- mum cardinality

15 1

of a vertex cut

5

^of G under the restriction that the set of neighbors of v is not contained in 5 for each vertex v in G was shown to be NP-complete [4].]

No\v, \\'e consider an n-d이lime히태ns히Jon퍼a떠1 hyperπrlωu배C l

prηro야v씨l버de an accurate deterministic measure of node fault tolerance in η­

cube networks

,

Esfahanian [3J proposed vertex connectivity of Qn under the restriction that at most n - 1 neigbbors of any processor may fail simultaneously (i.e., F does not contain the set of neighbors of any ver- tex in Qn). An exlension to this is vertex connectivity of Q" under the restriction that fol' a gi 、ren p (1

<

p

<

n)

,

at mosl p neighbors of any processor may fail simultaneously. This gives rise to the definition of a p-restricted cul. For a given p (1

<

p :S: n), a p-restricted cut F of Qn is a vertex cut of Q" such tha.t F contains a.t most p neighbors of each vertex in Qn, \ovhile a p-coηditional cut F of Qn is a vertex cut of Qn such tha.l F conlains at most p neighbors of each vertex in Qn - F 까'e denote the collection of a.ll rninimum cardinality p-restricted cuts (p-conditiona.l

culsι respectiveJy) of Qn by κ ( 11.， p) (F(n, p), respect.ively). In [5] it is shown that a p-conditional cut of Q" always exists and the cardinality

I FI

of F E F(n, p) is p2"-P, and tha.t for p = 2, Qn admits a p-res얀tr끼IC다ted cαωu바 Jt if anà on새1

grven

10 this paper, we obtain an upper bound and a sharp lower bound for the minul1lum cardinality of a p-restricted cut of Qn, and iIlvestigale the structure of F's in κ(n ， p). We denote by κ(n ， p) the cardinality

I FI

^of

FE

^{κ (11.，} p). In ~2， we sho\\' that Q" admits a p-restricted cut if and only i f n :S: 3p 一 2

,

and that κ (n， p) :::: p2^n-p when n :S: 3p - 2. We also show that (1) κ( '11.，])) = p2^n-p if and only ifn 으 3]) - 2, and n :S: 2p for l'

>

3, (1!) 2P

(nr앓

，)

:::: ^{κ(1시 p)}

^{when Jl}

^>

^{3 and 2])}

^<

^{n :S: 3p - 2. We then}

present for each )) and rr (1

<

p :S: n S 3p - 2, and n :S: 2]) for ])

>

3)‘

a cha.racterization of all rninimum cilrdinillity p-restricted cuts of Q^n- 1"

~3 ， we develop an a.lgorithm for finding all F's in κ (n ， p) for given n and p wbere 1 < p :S: n :S: :3p - 2

,

and n S 2]1 for ]1

>

3

Tbe vertices of Qn are distinctly labeled by binary n-tu

Restricted cuts in hypercubes 231

and two vertices are adjacent if and only if their binary labels differ in ex- actly one bit position. For a subcube W of Q"

,

V(W) denotes the vertex set of W. For a v E V(Q"), A (Q" : ν) denotes the set of all vertices which are adjacent to v in Q". Note that for each p (1

<

p :S n)

,

F E κ (n ， p)

(F

E .1"

(n ,

p)

,

respectively) if and only if

F

is a minimum cardinality

vertex cut of Q" Sl때 that IA(Q" : x)

n

FI :S p for all x E V(Q,,) (all x E V(Q^{,,) -} F^, respectively). For an X

c

V(Q^,,), [XI denotes the sub- graph of Qn inclucecl by X. For clisjoint vertex sets X, Y of Q^{" ,} X 8 Y denotes [X U Y

I,

where an eclge inciclent to a ve때x in X and to a vertex in Y is referrecl to as a CTOSS edge. For two disjoint subcubes 5 and T of Q" (i.e., V(5) and V(T) are disjoint), 5 8 T will mean V(5) 8 V(T). Two disjoint k-subcubes 5 and T of Q" are called a에 acent if 58 T ⁼ Qk+'; in this case, the one-to-one correspondence between V(5) and V(T) defined by cross edges is an isomorphism between 5 and T. For two (η - 1)- subcllbes Land RofQn with Q" = L8 Rancl asubcllbeX of L

,

X_R will denote the subcube of R corresponding to X

To facilitate our discussion we introduce tbe following decomposition of Qn by a subcube. For an (n - k)-subcube 5 of Qn (1:S k :S 미)，’ n w defìne A; (Q" : 5) (0 :S i :S k) by:

Ao

(Qn ^‘ 5)

=

^{5}; A

,

^{(Qn : 5)}

=

{W 1 W is an (n - k)-subcube of Qn, 58 W ⁼ Qn-k+d; for 2 :S i :S k

,

A‘ (Qn : 5) = {W 1 W is ^11.11 (71 - k)-s^lIbcube of Q^{" ,} W 8 U Qn-k+' for some U E A;^-1 (Qn : 5)} - A;^-2 (Qn ^‘ 5). Note that

I

A; (Qn ^‘ 5)1

(D ^,

^{0 :S i :S k}

^,

^{and if we} contract each (71 -

k샤샤;)↓)-cu뼈

l

10 ~i :S k서} to a s잉1l1g밍le ve히Iηtex t“띠hen tμhe resu비l니lμ…t“ω띠lIl g gr대때a이p이)h is Qk. Tbus

,

if A, B E A;(Q" : 5), A 츄 B (0

<

i

<

k) tben no vertex of A is ad jacent to a vertex of B. Note also that each member of A; (Q" : 5) (O:S i

<

k) is adjacent to k - i members of A;+

,

^(Q,

^‘

^{5). The above rep}rε:sentation of Q.

‘

by A; (Qn : 5)

,

0 ~ i :S k

,

is referrecl to as the decomposition of Qn by 5

,

and denOLed by Qn = Qk ^X 5. V(A; (Qn : 5)) (0 :S i :S k) will denote tbe set of 、ertices in A; (Qn : 5), i.e., V(A; (Q" : 5)) = U{V(W ) 1 W E A; (Q" : 5)}. [n 씨lat follows, A

,

^{(Qn : 5) ancl A2 (Qn :} 5) will be clenotecl by A(Q" : 5) ancl ß (Qn : S), respectively

2.

Minimum cardinality p ... restricted cuts of

Qn

We fìrst det.ermine all 71’s (1

<

p ~ n) for 、이lich Q" admits a p- restricted cul. (A similar situatjo^l1 cloes not arise for the case of p- conclitionaJ cut of Qn; in fact, for each p and 11 (1

<

p:S n), Q" admits a p-conditional cul 떼. )

232 A. Duksu Oh

Theorem 1. Lel p and n be inlegers

,

1 < p :S n. Then lhere exisls a

p-reslπ cied c-ut of Qn if and only if n :S 3p - 2

Proof Let n > 3p - 2

,

and suppose that there exists a. p^•restricted cu t F of Qn. Select two components C1 a.nd C2 of Qn - F, a.nd define 5 by 5

= min {d(" ， ν) 1 " E C1_‘ v E C2},

“

^here d( μ， ν) is the dista.nce between

" a.nd v in Qπ Let 5

=

^d("

,

v) where" E C" v 든 C2

,

^a.nd let X be the smallest subcube of Qn containing " and v. So

,

X is a 5-subcube of Qn

,

and note that A(X : ,,) U A(X : v) C F. h follows that 1 < Ó :S p. Also,

it follows from Qn = Qn-ó X X that IA(Qn : X)I = 11.- 5. Now

,

select a w E A(X : ,,), and write A(z) = {Y E A(Qn : X) 1 the vertex in Y corresponding to z is in F} where z E {ll

,

v

,

ω}. Since IA(Qn : z)

n

FI :S p and IA(X : u)1 = IA(X : v)1 = 5

,

、vesee that IA(u)l :S p - 8

,

IA(v)1 ::; p- 8 and IA(tι)1 :S p; thus IA(u) U A(v) U A(w)1 :S 3p- 28 :S 3p-2- 5 < 11.

Ó. Hence there exists a Z E A( Qn ^‘ X) such that {,,', v’, ψ'}

n

^F

= ø

where u', v' and w' are respectively the verlices in Z corresponding to ll, v and ω. This is a contradiction 10 the choice of u and v. 'vVe conclude tha.t if 11. > 3p - 2

,

Q" does not admit a p-restricted cut

Conversely

,

we construct a p-restricted cut of Q" for each n and p (p

:s

11. :S 3p - 2)

Case 1. n :S 2p For an (야n- p끼)샤)-su비l니，bcu때l

P:S n :S 2p

,

it follows from the structure of lhe decomposition Q" = Qp X 5 tbat F(S) is a p-restricted cut of Qn- Note t.hat IF(5)1 = p' 2n- p

Case 2. 2p < n.

Write Lo = Qn. For 1 :S k :S n-2p

,

let Lk a.nd Rk be (n-k)-subcubes of Lk-l such that Lk-l = LkOR k

,

^a.nd denote by fk the isomorphism from Lk to Rk defined by the cross edges. Note thal Lπ-2p = Q2p' Now

,

let S be a p.subcube of Ln-2p and write F(2p

,

i) = V(A; (Ln-2p : 5))

,

1

<

i :S n - 2p

+

^1. For 0 :S j :S n - (2p

+

1) and 1 :S i :S n - (2p

+

j)

,

define F(2p+ j

+

^{1,i) =} F(2p+ j,i) Ufn_2p_j(F(2p+ j ,i

+

^{1)). lt follows}

from the fact tha.t each member of A; (Ln-2p : 5) (0 < i < p) is adja.cent to i members of A‘

,

(L"-2p : S) and to p - i members of A‘+1 (L"_2p : S) that F(2p

+

j

+

1

,

1) is a. p-restricted cut of L,,-(2p+j+l), thus F(n

,

1) is a p-restricted cut of Q". This completes the proof.

We note that Theorem 1 includes tbe result for p = 2, obtained in [5]. Since every p-restricted cut of Qn is a p-conditional cut of Q"

,

it follows from Theorem 1 and Lemma 1 below that κ(n，p) 2: p2n- p wben p < η :S 3p - 2. Next

,

we determine n and p for which ^",(n

,

p) = p2n-p.

Restricted cuts in hypercubes 233

Lemma 1 ([히). Lel l' and n be inl ege^1'S

,

1 < p ~ π

1 I

^{F E F (n}

^, 1')

then IFI 二 p.2ⁿ- ^p

Lemma 2 ([6]). Lel F E F(ι

1'),

1 < l' ~ n

,

l' 켜 3. Then Qn - F has

tμ'0 compoηenls， ^Ol1e 01 which. is an (11 - p)-subcube

5

01 Q" and F =

V(A(Qn : 5))

Le밍mma 3 (이[π[7]끼께]). Let F E ηrF디(야nπ. 3이)

,’

3 ':; n^’ T，ηT끼her사! Qn - F h. a따s two

nenη ls and onc 01 the lollowing holds

(i) One compone띠 01 Qn - F is an (n - 3 )-subcube 5 01 Qn and F = V(A(Qn : 5))

(μ) Th.el'e exist (n - 1 )-subcubes L and R 01 Q

’ ‘

ψith Q" = L 8 R such that F

=

V(A(L : X )) U V(ß(R: X_R)) 101' somc (n - 4)-subcube X 01 L.

Theorem 2. Lel 1

<

l' .:; n ~ 3

1' -

2. Then:

(i) ^,,(n

,

p) ~ p2"-p.

(ii) κ(n ，p)

=

p2"-P il and only iln ~ 2

1'

or l'

=

^3.

(iii) 2P .

(，，~:삶1 ) ~

^,,(n,p)

ψ삐

^l' > 3 and 2p

<

n

Pmof

m(η)

(1) ^{Assume fi}Theorem l ^{rst thal} and

Lemr

ⁿ

^<

^{2p. From the proof} of Theorem 1

,

there exists a p-restricted cut F of Qπ with IFI = p.2"-p. Thus

,

κ (n ， p) = p2"-P

Next

,

let l' = 3. \싸 need only show that ".(7

,

J) 3 . 2⁴ Select an F E F(7

,

3) such that Lemma 3 (α) holds for F. S ince F is also a 3- restricted cut. 이 Q

,

^{and \FI}

⁼

^3.24

^,

^{、vesee that κ(7， 3)}

⁼

^{3.24 Conversely}

^,

assume ,,(n

,

p) = p2n-". Then K(n

,

p) C F(n

,

p) by Lemma J. Jf l'

i

3 and 11

>

2

1' ,

lhen lhe structure of any F

ε

^{F (n}

^,

^{p) (Lemma 2) sllO}

”

F ls not a p restrlCled cut of

Q ’ ‘’

a contradiction. llencc

,

n .:; 2p or l' = 3

(iη) ln the proof of Theorem 1, we have construcled a p-restricted cut F(n

,

l) of Q,,; from the construction of F(n

,

1) we have IF(n

,

1)1 = 2^{p •} (μ‘

앓

，

) ，

^{and thus} 2^{p •}

( ζ삶

，

) ~

^,,(n

,

p). The proo[ is now complete

Rema^1'k. Theorem 2 (ii) includes t.he result for l' = 11 - 1, obtained in [31 Theorem 2 (ii) sh。、‘s 1hat. for gi ven η and l' (1

<

l' ~ n .:; 3

1' -

2

,

and 11 ~

2

1'

for p

>

3), the n-cube nelworl、 can tolerate up 10 p2n-p - 1 processor

failures and remains conned ed provided that al most l' neighbors of any processor are allowed to fail.

We next eslablish lhe following characteriza.tion of all F's in κ(n，p)

when 1 < l' ~ n ~ 3p - 2, and n ~ 2

1'

for l'

>

3.

234

A .

Duksu Oh

Theorem 3. Let 1

<

p :S n :S 3p - 2

,

^aπd n :S 2p for p

>

3. Theπ

(1) lf p

f-

3 then κ (n，p) = {V(A(Qn: 5))

I

5 ;s an (n - p)-subcube of Qn}.

(2) lf n :S 6 then κ (n ， 3) = {V(A(Qn : 5))

I

5 is an (n - 3)-subcube ofQn} ^U {V(A(L: X)) ^U V(B(R: X n))

I

L and R are (n -1)-subcubes ofQn with Qn

=

L 0 R

,

X is an (n - 4)-subcube of L}.

κ(7 ， 3) = {V(A(L: X)) U V(B(R ^‘ X n ))

I

L and R al'e 6-subcubes OfQ7 with Q7 ⁼ L 0 R

,

X is a 3-subcube of L}.

Proof By Theorem 2 (ii) and Lemma 1

,

we bave κ(n ， p) C ;:(n

,

p) If p

f-

3 and F E κ (n ， p) tben by Lemma 2

,

F = V(A(Qn : 5) for an (n - p)-subcube 5 of Qn. Note by Lemma 3 tbat κ(7 ， 3) consists of all F’s in ;:(7

,

3) such that Lemma 3 (ii) holds for F. Now

,

let F E κ (n ， 3)

By Lemma 3

,

we conclude that if 11 :S 6 then one of the following (i-ii) holds

,

while if n = 7 then only (ii) holds

(i) F ⁼ V(A(Qn : 5)) for an (n - 3)-subcube 5 of Qn.

(ii) There exist (n - 1 )-subcubes L and R of Qn with Qn ⁼ L 0 R such tha.t F = V(A(L : X )) U V(B(R : X n)) for some (n - 4)-subcube X of L.

Conversely, write F(5) ⁼ V(A(Qn : 5) where 5 is an (n - p)-subcube of Qn; in addition

,

fol' ])

=

³

,

、vrite F(X

,

L

,

R)

=

V(A(L : X)) u V(B(R X n )) ^where L and R are (n -I)-subcubes of Qn with Qn = L 0 R

,

X is an (n - 4)-subcllbe of L. Note that F(5) is a p-l'estricted cut of Qn for (n

,]))

￥ (7

,

3)

,

、.vhile F(X

,

^L

,

^R) is a 3-restricted cut of Qn. Since IF(5)1 = ])2"-p and IF(X

,

L

,

R)I ⁼ 3.2"-3

,

Theorem 2 (ii) implies F(5) E κ(n ，]))

for (11

,]))

￥ (7

,

3)

,

and F(X

,

L

,

R) E κ (n，3). This completes the proof

Let])

>

3 and 2p

<

n :S 3])-2. 1n this ca.se

,

it seems t,hat characterizing a.ll F

’

^Slll κ (n ，7') is diffìc^lIlt. Theorem 2 (iii) gives an upper bound for

"'(11

,

p). For the question about the exact value of κ( 11.，]))， we propose the following conjedure

Conjecture. If l' > 3 and 2])

<

11 :S 3]) - 2

미en κ(11， p)=2

^P

.(’‘j삶

1

)

3.

AIgorithm for finding minimum cardinality p- restricted cuts of Qn

Using the characterization of κ (n ，])) (Theorem 3), we have the f，아

lowing algorithm for finding all F's in κ (n，])) for given 11 and p ι，here

1

< ])

:S 11 :S 3]) - 2, and ¹¹ :S 2]) for ])

>

3

Algorithm minimum cardinality p-restricted cuts of Qn

Restricted cuts in hypercubes 235

(version 1)

Input: Qn and an integer p (1

<

p :::: n :::: 3p - 2, and n :::: 2p for p

>

3) Output: κ (n，p)

1. Let κ =0;

2. If (n

,

p) 카 (ï

,

3) then

for each (n - p )-subcube 5 of Qn do begin

F • V(A(Qn : 5));

κ • κ u {P};

end

‘

if p = 3 then

for each pair of (11. - 1 )-sllbcubes L and R of Qn with Qn ⁼ L 8 R do

for eacb

(n -

4)-subcllbe X of L do begin

F • V(A( L : X)) U V(ß(R: Xn)); κ ← κ u {P};

end;

3. Return (κ (n ， p) • κ)

Next, we construct all F's in lC(n,p) for each n and p (1

<

P

<

n :::: 3p - 2

,

and n :::: 2p for p

>

3) usi ng the charaderization of κ (n ， p)

(Theorem 3), and then present a concrete 、 ersion of the above algorithm.

For a k E {O

,

I}, k denotes the complement of k. Let {i"i2

, ...

，써 C {1

,

2

,‘ ,

n} (i

,

< i2 < ... < ip). For each (C"C2''''

,Cp )

E V(Qp)

,

let

C(Cl

,

C21"" Cp ) =

{(Cï,

C2"" 'Cp )

,

^(C)

,

C2)""Cp )

,‘

’(Cl

,

^{C21 ...} ，강)} and write 5(n; i11 .•.

,

^1:p ; C)

’ ‘ ’

^Cp ) = {(x

,‘

^’

,

^Xn) ^E V(Qn)

I

Xi

,

^{= Ck} for k =

l

,

2

, ... ,

p}, and dcfìne F(n; i" ...

,

ip ; c" ...

,

cp ) by:

F(n; i" ...

,

ip; c" ...

,Cp)

⁼ U{S(n; ^{1" ...}

,

^lp; d" d2

, ... ,

^dp )

I

(d"d2

, ... ,

dp) E C (C"C2" "'Cp )}

Observe lhat 5(n; i" ...

,

i

, ,;

c" ...

,

cp ) is the vertex set of a.n (n-p)-subcllbe

。 [ Qn and conversely the vertex scl of each (n - p)-subcube of Qn is of the [orm 5(η i]，

... ,

ip ; C)

, .. "

cp )

,

aJso note tha.L F(n; i)’“ Zp; Cl1 •••

,

cp )

is the set of all vertices in A(Qn: [5(11.; i" ...

,

^{lp; C" ‘} ’ C_{p )}]). By Theorem 3

,

we conclude that if p

f

3 then κ(n， 1') consists of a.1I F’s of the form

F(n; it1 .•• ,ip ; Cl: ... ,cp )‘

For p = 3

,

we use additional notations: Let 8 E{O

,

1}. For each j E {1

,

2

, ... ,

n}

,

write 5(n

,

j

,

8) ^{= {(Xl}

’

‘X,,) E \f(Qn)

I

^{Xj =} 8};

236 A. Duksu Oh

for each (C"C2

,

C3) E V(Q3)

,

let CO(CI>C2

,

C3) = {(히， C2 ， C3)' (Ct ，감， C3)

,

(cμC2 ，전)} and

C ,

(C" C2

,

C3) = {(하，강， C3) ， (하， C2 ，전)， (C" 갈，강)}. Now

,

for each j E {1

,

2

, .. . ,

n} - (i"i2 ， 씨 and (C"C2

,

C3) E V(Q3)

,

write S(n; 1:" ι ;3; C"C2

,

C3; j

,

8) ((.1:t, ...

,

Xn) ^E S(n

,

^j

,

8) ¹ Xi

,

Ck for k = 1

,

2

,

3}, and define F(n; i" i2

,

_i3; C"C2

,

C3; j

,

6) by

F(n; i"i2

,

13; C"C2

,

C3; j

,

8) = U{S(n; _l"i2

,

i3; d"d2

,

_d3; ^j

,

6) ¹ (d" d2

,

d3) ^E C6( ^C" C2

,

C3)}

Observe that S(n

,

j

,

6) is the vertex set of an (n-l )-subcube of Qn

,

and the vertex set of each (n - 1)-subcube of Qn is of the form S(n

,

j

,

8)

,

and that Qn ⁼ [S(n

,

j

,

0)] 8 [S(n

,

j

,

1 )]. Also note that the 、ertex set of each (n - 4)-subcube of [S(n ， ι8)] is of the form S(n; _{i l}

,

12

,

_i3; Cl

,

C2

,

C3; j

,

6).

From the structure o[ the decomposition [S( n

,

^j

,

6)] = Q3 X [S( n; 1" i 2

,

13;

C" C2

,

C3; j

,

6) ], we see that F(n; i" ;2

,

i3; C" ^C2

,

C3; j

,O)

is the set of all vertices in A([S(n

,

j

,

O)]: [S(n; _i"i2

,

_i3;CI

,

C2

,

C3; j

, O )]) ,

and F(n; il

,

_{i 2}

,

_i3;

C" C2

,

C3; j

,

1) is the set of all vertices in ß([S( n

,

j

,

1)] : [S( n; i" i2

,

잉 Cl

,

C2

,

C3; j

,

I)]). By Theorem 3

,

we conclude that if n :<::: 6 then κ(n ， 3) consists of all F

’

s of the form F(n; i" 12

,

13; CI

,

C2

,

C3) and all F

’

s of the form U{F(n; i,,12

,

13; C"C2

,

C3; j

,

6)

18

⁼ O

,

l}; while κ(7 ， 3) consists of all F's of the form U{F'(n; il

,

;2

,

;3; CI

,

C2

,

C3; j

,

6)

18

⁼ 0

,

1}

This completes the co따t. ruction of all F'

’

^{S 111 κ (n，} p) for each n and p (1 < p :<::: n :<::: 3p - 2

,

and n :<::: 21' for p

>

3)

,

which also establishes the following concrete version of the above algorithm ^[01' finding al1 F’S Il1

κ (n，p).

Algorithm minimum cardinality I'-restricted cuts of Qn (version 2)

lnput: Qn and an integer p (1 < l' :<::: n :<::: 3]) - 2, and ^11. :<::: 21' for p

>

3) Output κ (n ， p)

1. Let κ =

ø ;

2. For each {i"i 2

, .. . ,

ip} C {1

,

2

, ...

^‘ n} (il<i2< ... <ip) do for each (cμ C2, ... ,cp) E V(Qp) do

begin

if (n,])) 낯 (7,3) then begin

let C = {(긴， C2’ “’cp )

,

(C)

,

C^{'4h ...}

,

Cp)

, ...

， (Cl ，C2)"" 강)};

F • ((Xt,X2""'Xn) E V(Qn) ¹ (Xi"Xi" ...

,

Xip ) E C};

κ ← κU {F};

end;

Restricted cuts in hypercubes

if p

=

^{3 then}

begin

let C o = {(잔 ， C2， ^C3), (Cl' 깐， C3), (c" c" C3)};

let C

,

^{= {( c" 전， C3), ( Cl , C2, C3), (Cl ， 강，감)};}

for each j E {1,2, ... ,

n} -

{i"i"i3} do begin

237

Fo • {(XJ, X" ... ,Xn ) E V(Qn)

I

^{Xj =} 0, (x;p 자 ， Xi3) E

C

_o};

end encl:

F

,

^{• {(Xj,}X" ... ,Xn ) E V(Qn)

I

^Xj

=

¹, (Xip X‘²,_{Xi 3)} E

Cd;

κ ← κU {Fo

U

^Fd;

end

3. Return (κ (n，p) • κ)

References

(1] F. Harary, "Conditional connectivitι" Nefworks, vol. 13 pp. 346-357, 1983 [2] A. Es[ahaniall and S. Hakimi, “On computÎng a conditional edge^•connectivity of

a graph,’ Jnfonnalio1/. Processing Letfers, vol. 27, pp. 195^•199, 1988

[3] A. Esfahanian, ‘ Generalized meas.ures of fau lt tolerance with application to n-

cube nebvorks ’ IEEE Tmnsactions 011 Computers) \'01. 38, 1I0.1l, pp. 1586^•1591,

1989

[4] A. D. Oh, H.-A. Choi, and A. Esrahanian, “Somc results on generalized connec- tivity wiLh applications to topological design of rault-LoJerant multicomputers,’ J

0/ Combinofo^l"iai Mathematics ilnd CombinafonaJ Compuling, vol. 13 pp. 39-56,

1993

[5] A. D. Oh and Il.-A. Choi, ‘Gcnera.lized measures of fault tolerance in ^l1-CU be networks," JEEE Transacfzons 011. Parallel and Distribuled Systems, vol. 4, no. 6,

pp. 702-703, 1993

[6] A. D. Oh and H.-A. Choi, ‘ On Generalization of vertex connecti、ity in n-cube netwürks,’ Proceedings 01 lht Sevcnth Inierll 이 iOflal ConJerence 0/1. Graph Theory,

Combinatoric$. Algol1'thmB, ^(l.lld Applicai.lolls) \Vestern "Michigan Univcrsity, 1992 [7] A. D. Oh, “Conditional cuts in hyperc뻐es，" Congπssus IVumerantium. vo1. 96,

pp. 39-46, 1993

DEPARTMENT OF ìvIATHEMATTCS AND COMPUTER SCIENCE, ST. MARY’S COLLEGE OF MARYLAND, ST. MARY’S CITY, MD 20686, U.S.A