On embeddings of hamiltonian paths and cycles in Extended Fibonacci Cubes

INTRODUCTION

An interconnection network consists of a set of processors, each with a local memory and a set of bidirectional (or unidirectional) links that serve for the exchange of data between processors. Interconnection networks are represented by undirected (or directed if the links are unidirectional) graphs G = (V, E) where V is the set of nodes, each node corresponding to a processor and E is a set of edges, each edge corresponding to a link. Some of the key features of interest in such an interconnection network are its topological properties as node degree, diameter, connectivity, structure, the embeddability of other topologies and the communication algorithms.

A number of interconnection topologies (1), (3), (5), (9) have been proposed in the literature. A widely studied interconnection topology is the hypercube, or the n-cube [H.sub.n]. The hypercube has good properties such as symmetry, small diameter and node degree, recursive structure, efficient communication algorithms. A drawback in the case of the hypercube is the number of nodes which is a power of 2 and limits the choice for a network interconnection with a given number of nodes.

Hsu (5) proposed and studied the properties of a new interconnection topology called Fibonacci cube based on the Fibonacci numbers. The Fibonacci numbers are defined as [f.sub.0] = 0, [f.sub.1] = 1, [f.sub.n] = [f.sub.n-1] + [f.sub.n-2], for n>1. The Fibonacci cube of order n has [f.sub.n] nodes, n>1, where [f.sub.n] is the n-th Fibonacci number and the nodes can be labelled with binary strings of length n-2 with no consecutive 1's. Two nodes are connected if their labels differ in exactly one position. It is clear that a Fibonacci cube can be seen as resulting from a hypercube after some nodes become faulty. The Fibonacci cube can emulate many of the basic algorithms for the hypercube and there are more Fibonacci numbers in a given interval than powers of 2.

Wu (11) generalized the Fibonacci cube topology by defining the series of Extended Fibonacci Cubes, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The Extended Fibonacci Cubes are also defined using the same recursive relation as the Fibonacci numbers, but changing the initial conditions. In this way the number of choices for the number of nodes for an interconnection network increases. The topological properties and embeddings in Extended Fibonacci cubes were studied (6), (8), (11). In this research we will define a Gray code for extended Fibonacci cubes and using this code we will define a hamiltonian path in an extended Fibonacci cube.

FIBONACCI CUBES AND EXTENDED FIBONACCI CUBES

The Fibonacci Cube topology is based on the properties of Fibonacci numbers. The Fibonacci numbers are defined as [f.sub.0] = 0, [f.sub.1] = 1, [f.sub.n] = [f.sub.n-1] + [f.sub.n-2], for n>1. According to Zeckendorfs lemma any integer number k, 0[greater than or equal to]k<[f.sub.n] can be written as a sum of Fibonacci numbers as it follows:

K = [n - 1.summation over (i = 2)][b.sub.i]*[f.sub.i], [b.sub.i][member of]{0,1},[b.sub.i]*[b.sub.i + 1] = 0,i = [bar.1,n - 2]

This means that to every integer number k, 0[greater than or equal to]k<[f.sub.n], we can associate a Fibonacci code [k.sub.F] = [([b.sub.n-1] ... [b.sub.3][b.sub.2]).sub.F] according to its representation as a sum of Fibonacci numbers. This code is a binary code which has no two consecutive l's and is called Fibonacci code. Any binary string with no two consecutive l's is called Fibonacci string.

The Fibonacci cube can be defined as follows:

Definition 1: The Fibonacci cube of order n>l, denoted by [[GAMMA].sub.n], is defined as [[GAMMA].sub.n] = ([V.sub.n], [E.sub.n]) where the set of nodes is [V.sub.n] = {0, 1,..., [f.sub.n]-l} and the set o f edges [E.sub.n] is [E.sub.n] = {(i, j)|H([i.sub.F], [j.sub.F]) = 1, i, j[member of][V.sub.n]}, where H([i.sub.F], [j.sub.F]) is the Hamming distance between the Fibonacci codes of nodes i and j.

The Fibonacci cube of order n has [f.sub.n] nodes and there is an edge between two nodes if their Fibonacci codes differ exactly in one position. The Fibonacci cubes of order 2, 3, 4, 5 are represented in Fig. 1. A recursive definition for the Fibonacci cubes has been given (5) as follows:

[FIGURE 1 OMITTED]

Definition 2: The Fibonacci cube [[GAMMA].sub.n] = ([V.sub.n], [E.sub.n]) of order n, n>l, is defined recursively as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [V.sub.n-1] and [V.sub.n-2] are the set of nodes of the order n-1 respectively n-2 Fibonacci cubes and [parallel] denotes the concatenation of strings and there is an edge between two nodes if their binary representations differ exactly in one position. The initial conditions are [[GAMMA].sub.2] = ({[lambda]}[empty set]) and [[GAMMA].sub.3] = ({0,l}, {(0,1)}).

A Fibonacci cube of order n, [[GAMMA].sub.n], has [f.sub.n] nodes and can be recursively decomposed in two Fibonacci cubes of order n-1 and n-2. The two [[GAMMA].sub.n-1] and [[GAMMA].sub.n-2] are connected by [f.sub.n-1] edges. The Fibonacci cube has good properties: the nodes degree is between n/8 and n-2, the diameter is n-2, the node and edge connectivity are between n/8 and (n-2)/3 respectively, basic topologies such as arrays, rings, meshes, hypercubes can be embedded in Fibonacci cubes. But just the Fibonacci cubes with an even number of nodes, greater than 2 are hamiltonian.