, 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.