U f0,1g
n
, that is, U is a set of some binary strings of
length n. Then, we use 0U to denote the set {0u|u 2 U}.
Letting P∶u = u
(0)
, u
(1)
, …, u
(k)
= υ denote a sequence
between u and υ, where u
(i)
is a binary string of length n for
any i 2 {0, 1}, we use iP to denote the sequence iu = iu
(0)
,
iu
(1)
, …, iu
(k)
= iυ for any i 2 {0, 1} and use rev(P)to
denote the path υ = u
(k)
, u
(k – 1)
, …, u
(0)
= u. Given u =
u
n – 1
u
n – 2
… u
0
2 V (TQ
n
), for 0£i£n – 1, we define
ðu,iÞ¼u
i
u
i – 1
u
0
, where is the exclusive
operation.
The n-dimensional twisted cube, denoted by TQ
n
,isan
n-regular graph of 2
n
nodes, which can be recursively
defined as below [16].
Definition 2 The 1-dimensional twisted cube TQ
1
is
defined as the complete graph with two nodes labeled 0
and 1. For an odd integer n≥3, TQ
n
consists of four
subcubes TQ
00
n – 2
, TQ
01
n – 2
, TQ
10
n – 2
, TQ
11
n – 2
, where TQ
ab
n – 2
is isomorphic to TQ
n – 2
and VðTQ
ab
n – 2
Þ¼fabxjx 2
V ðTQ
n – 2
Þg and EðTQ
ab
n – 2
Þ¼fðabx,abyÞjðx,yÞ2EðTQ
n – 2
Þg
for a, b 2 {0, 1}; and V ðTQ
n
Þ¼
[
a,b2f0,1g
V ðTQ
ab
n – 2
Þ,
EðTQ
n
Þ¼
[
a,b2f0,1g
EðTQ
ab
n – 2
Þ[E
#
, where for the nodes u =
u
n – 1
u
n – 2
… u
0
, υ = υ
n – 1
υ
n – 2
… υ
0
2 V (TQ
n
), (u, υ) 2 E',
if u and υ satisfy one of the following three conditions:
1) u ¼
υ
n – 1
υ
n – 2
υ
n – 3
υ
0
;
2) u ¼
υ
n – 1
υ
n – 2
υ
n – 3
υ
0
and ðu,n – 3Þ¼0;
3) u ¼ υ
n – 1
υ
n – 2
υ
n – 3
υ
0
and ðu,n – 3Þ¼1.
Figure 1 demonstrates the 3-dimensional twisted cube
TQ
3
and the 5-dimensional twisted cube TQ
5
.
3 Restricted connectivity of twisted cubes
In this section, we discuss the connectivity of twisted
cubes under the condition that each node has at least one
fault-free neighbor. In the following, for any integer, n≥1,
we always use F to denote the faulty set of nodes in TQ
n
.
Definition 2 gives the definition of TQ
n
for any odd
integer, n≥1. However, there is no definition of TQ
n
for
any even integer, n≥2. In this paper, for convenience of
presentation, we extend the definition of TQ
n
to any
integer, n≥1, as follows.
Definition 3 TQ
1
is the complete graph on two nodes
whose addresses are 0 and 1. For any integer, n≥2,
(a) if n≥2 is even, then TQ
n
consists of two subcubes
TQ
0
n – 1
and TQ
1
n – 1
. The most significant bit of the nodes of
TQ
0
n – 1
and TQ
1
n – 1
are 0 and 1, respectively. Two nodes u =
u
n – 1
u
n – 2
… u
1
u
0
and υ = υ
n – 1
υ
n – 2
… υ
1
υ
0
in TQ
n
,
where u
n – 1
¼ u
n – 1
¼ 0, are joined by an edge in TQ
n
if
and only if u ¼
υ
n – 1
υ
n – 2
υ
n – 3
υ
0
;
(b) if n≥3 is odd, by changing each node, u
n – 2
u
n – 3
…
u
1
u
0
, in TQ
n – 1
into a node, u
n – 2
0u
n – 3
… u
1
u
0
, in TQ
n
, we
obtain a single graph, denoted by TQ
0
n – 1
; by changing
each node u
n – 2
u
n – 3
… u
1
u
0
in TQ
n – 1
into a node
u
n – 2
1u
n – 3
… u
1
u
0
in TQ
n
, we obtain the other graph,
denoted b y TQ
1
n – 1
. TQ
n
consists of two subcubes
TQ
0
n – 1
and TQ
1
n – 1
. Two nodes, u ¼ u
n – 1
u
n – 2
u
1
u
0
2
V ðTQ
0
n – 1
Þ and υ=υ
n – 1
υ
n – 2
υ
1
υ
0
2 V ðTQ
1
n – 1
Þ, are
joined by an edge in TQ
n
if and only if one of the
following two conditions holds:
1) u ¼
υ
n – 1
υ
n – 2
υ
n – 3
υ
0
and ðu,n – 3Þ¼0;
2) u ¼ υ
n – 1
υ
n – 2
υ
n – 3
υ
0
and ðu,n – 3Þ¼1.
By Definitions 2 and 3, we have the following lemma.
Lemma 4 For any integer n≥1, if n is odd, the
definition of TQ
n
in Definition 2 is equivalent to that of
TQ
n
in Definition 3; if n≥2 is even, then TQ
n
ffi TQ
i
n
ffi
TQ
0i
n – 1
[TQ
1i
n – 1
for any i 2 {0, 1}.
Fig. 1 (a) 3-dimensional twisted cube TQ
3
; (b) 5-dimensional
twisted cube TQ
5
, where the end nodes of a missing edge are
marked with arrows labeled with the same letter
Jianxi FAN et al. One-to-one communication in twisted cubes under restricted connectivity 491