, is in use as the interconnection network of
massively parallel computers. In order for such computers to run parallel algorithms designed for cycle topologies it is necessary to embed a cycle in the hypercube. In the language of graph embedding, constructing a Hamiltonian circuit in a graph is the same a finding an optimal dilation-1 cycle embedding in that graph. Much work has been done in the area of graph embedding as related to interconnection networks, see [7] for a survey. The hypercube is known to have many labeled Hamiltonian cycles, for bounds see [3], and is even Hamiltonian decomposable, see [1]. The latter implies that a
missing at most 
edges is still Hamiltonian. The algorithm
presented here specifies a nonfaulty Hamiltonian cycle in a 
with twice as many (i.e. n-2)
faulty edges. Since 
is
regular of degree n this is optimal in the most general case. That is, if
faulty edges are
incident to a single vertex the graph surely has no fault free Hamiltonian
circuits.
is defined
recursively as a cartesian product of graphs as follows:
to have vertex labels 0 and 1,
then 
is a labeled graph
whose vertex set, 
consists of the 
binary
n-tuples, and two vertices are adjacent if and only if their vertex
labels differ in exactly one coordinate. In particular 
is regular of degree n, has order 
, and size 
. The vertex 
, has 
for 
, called the 
coordinate of v, or the coordinate of
v in the 
dimension. Label the edge set, 
, by all n-tuples in the ternary alphabet
with X appearing
in exactly one coordinate. We will call the edge 
on a vertex v the i-edge of
v. Each vertex has one i-edge for each 
. For example, the edge label 0110X10
describes the edge incident to the vertices with vertex labels 0110010
and 0110110, and is an edge in the 
dimension, or a 2-edge in 
.
are denoted as follows. Since there is a unique
i-edge, 
, at each
vertex in 
, one can
completely describe any walk in 
by specifying a starting vertex, v, and a
sequence listing the dimensions of the edges to be used in order starting from
v. For instance the starting vertex v=10001 and the dimension
sequence s=0,4,2,2,3 describes the walk of length 5 having the edge label
sequence:
, 
will denote the edge label sequence of the
specified walk. One could similarly define vertex label and vertex/edge label
sequences.
can
be visualized as two 
joined in a pairwise fashion. Specifically, create the new 
dimension on the vertex labels of the two
smaller cubes and assign 1's to the new coordinates in one 
and 0's to the new coordinates in the
other. Then add 
-edges
between vertices of the two cubes if and only if their vertex labels differ in
exactly the 
coordinate.
Similarly one can view 
as two 
joined along
dimension i, for any 
, where vertices in the two smaller cubes have
constant 
coordinates.
So a Hamiltonian path in 
can be formed by connecting up identical
Hamiltonian paths in the two 
with an i-edge at either end of the
paths.
labeled as described above is necessarily
a Gray code, that is a sequence of all 
binary n-tuples such that successive
labels (including the first and last) differ in exactly one coordinate. When the
path is constructed recursively from identical Hamiltonian paths in cubes of
smaller dimensions as described above the path is called a reflected Gray code
Hamiltonian path. Since a reflected Gray code Hamiltonian path has the property
that the end vertices are adjacent, adding the edge between them gives a
reflected Gray code Hamiltonian circuit.
. One can define dimension sequences for
reflected Gray code Hamiltonian circuits in 
as follows.
be a permutation
on the n letters 
and define 
for 
The reflected dimension sequence 
with respect to the
permutation 
is defined
in [6] as follows:
, the set of edges in 
, is a Hamiltonian circuit.
Lemma 3.2 on Hamiltonian circuits follows immediately from lemma 3.1 on
Hamiltonian paths.
be a
vertex label in 
, and
. Without loss of
generality we can assume 
and 
. Then 
, and, 
consists of the edges 
, is a Hamiltonian path, and the end vertices are
adjacent in the 
-dimension as required.
, a vertex 
of the cube, and a permutation on
N+1 letters 
.
Think of 
as two 
, 
and 
where the vertex labels of 
have constant entries 
as the 
coordinate (i.e. v is in 
), and the vertex labels of
have constant entries
as the 
coordinate. Then 
edges connect vertices in
the two cubes which differ in exactly the 
dimension.
dimension
on all vertex labels in 
and truncate our permutation to 
By induction the Hamiltonian path in 
starting at v, 
contains:
-edges with
in the 
dimension,
-edges, 
, with a 
in the 
dimension, and 
in the 
dimension for 
, and with 
in the 
dimension.
is a
Hamiltonian path in 
,
and its end vertices v and u differ only in the 
dimension.
, the
Hamiltonian path in 
which came from the first 
of the dimension sequence 
is complete, and ends at the vertex
u which differs from v only in the 
dimension. Take the 
edge (the next edge in the sequence 
) over to the other cube,
, to arrive at the
vertex 
which differs
from v exactly in the 
and 
dimensions. Apply the induction hypothesis
again, this time in 
with starting vertex 
,
again ignoring the 
dimension on all vertex labels. By induction 
contains:
-edges with
in the 
dimension,
-edges, 
, with a 
in the 
dimension, and 
in the 
dimension for 
, and with 
in the 
dimension.
is a
Hamiltonian path in 
,
and its end vertices 
and 
differ only in the
dimension.
are exactly the type i and
ii edges lemma 3.1 specifies. The edges with a 
in the 
dimension are in 
by the inductive hypothesis in 
, and the edges with a 
in the 
dimension are in 
by the inductive hypothesis in 
, and lastly the one 
edge from u which
differed from v only in the 
dimension is in 
as required. To wit the path is Hamiltonian,
and the end vertices v and 
differ only in the 
coordinate.
-edge at v to
complete the Hamiltonian circuit. This edge is listed with the 
-edge at u in iii of lemma
3.2.
,
produces a permutation 
and a vertex 
such that
the Hamiltonian circuit 
contains no edges of F. Array indexing
starts at 1, and although in practice it may be useful to use arrays for
and v, the
earlier conventions are used here for ease of proof. The parameter r is
introduced in the algorithm, where r is the number of fault-free
dimensions in F. 
.
, and a starting vertex 
of 
.
to be the edge-labels of F;
to the
r indices i so that column 
of FE contains no X's, and 
;
to the
n-r indices i so that column 
of FE contains at least one X,
and 
;
so that
is the number of
X's in column 
of
;
of v to 0;
; endfor
; endfor
do
;
;
. Since 
is already set, there is an s such that
, i.e. the 
row of FE is a 
-edge. We then set 
, the 
coordinate of v, to the opposite
of the 
coordinate of
this faulty 
-edge.
and the definition of FR, r is the smallest number for which there
is a 
-edge in F,
and the loops are set so that for each 
the inner loop runs 
times. Hence on the inner loop for any fixed
value of the outside loop counter i, s has constant value 
while if we define 
, t ranges from
note that
for any i, 
,
or
such that 
, but 
, so 
. Then substitution for r yields
by
definition of the M array. So 
whenever the line 
is executed.
is
the set consisting of:
-edges,
-edges, 
, with a 
in the 
dimension, and 
in the 
dimension for 
,
-edges with
in the 
dimension for 
.
and FR, there are no 
-edges in F for 
. This is because FR holds the
r column indices of FE which have no X's, these are then
used to set 
through
to faultless
dimensions. Note also that 
with equality only when no two edges of
F lie in the same dimension.
edges in F by
the above reasoning. Now Lemma 3.2 implies that 
contains all 
-edges with 
in the 
coordinate for 
, i.e. the 
-edges in 
agree with v in the 
dimension for 
. But for each 
-edge, 
in a row k of FE, 
, that is the 
coordinate of v is
such that v and the 
-edge differ in the 
dimension. Since 
whenever the above line is executed there are
no edges of type ii in F.
-edges in 
agree with v in the 
dimension for 
, but for each 
-edge in F a 
coordinate of v,
where again 
, is set so
that v and the 
-edge differ in the 
dimension. Hence, there are no edges of type
iii in F.
comparisons.
The v array is initialized to zero, this loop takes n+1
comparisons. The arrays FR, X, and M are initialized with
two nested for loops. This requires 
comparisons for the loop counters, 
comparisons to check if an
entry in FE is an X, and n comparisons to check if any dimension
has faults (i.e. check a flag) for a total of 
comparisons. The coordinates of v are
now set with 2 nested for loops that traverse the faulty columns of FE
with a conditional to check for faults. The worst case here is when there are
n-2 faulty dimensions, then there are 
comparisons. The algorithm is finished, the
total number of comparisons used is a polynomial of degree two in n,
therefore GET_PI_GET_V(F) has 
time complexity measured by the number of
comparisons.
,
GET_PI_GET_V(F) initializes FE to
to
and v go in the reverse order,
specifically 
and 
to see that the line
coordinates of v for 
so
is set to 1
and v. By lemma 3.2 the edges in 
are
-edges,
-edges, 
, with a 
in the 
dimension, and 
in the 
dimension for 
,
-edges with
in the 
dimension for 
.
. An alternative method of listing these edges
would be to write the edge label sequence 
. This could be done by writing out the
reflected dimension sequence 
and proceeding edge by edge from v. The
dimension sequence is as follows.
specifies a Hamiltonian cycle in 
avoiding a set F of
n-2 faulty edges in 
time.
, with at most 2n-5 faulty edges, in
which each vertex is incident to at least two nonfaulty edges, has a Hamiltonian
circuit consisting of only nonfaulty edges. This is optimal, since a 
with 2n-4 faulty
edges, in which each vertex is incident to at least two nonfaulty edges may have
no fault-free Hamiltonian circuit. The theorem is nonconstructive, but it nearly
doubles the number of faulty edges. A next step might be trying to write a
polynomial time algorithm to find the circuit guaranteed by [2].
International Symposium
on Fault-Tolerant Computing,(1992), 178-184.