Research Article Open Access

On Embeddings of Hamiltonian Paths and Cycles in Extended Fibonacci Cubes

Ioana Zelina1, Grigor Moldovan1 and Ioana Tascu1
  • 1 ,
American Journal of Applied Sciences
Volume 5 No. 11, 2008, 1605-1610

DOI: https://doi.org/10.3844/ajassp.2008.1605.1610

Published On: 30 November 2008

How to Cite: Zelina, I., Moldovan, G. & Tascu, I. (2008). On Embeddings of Hamiltonian Paths and Cycles in Extended Fibonacci Cubes. American Journal of Applied Sciences, 5(11), 1605-1610. https://doi.org/10.3844/ajassp.2008.1605.1610

Abstract

The interconnection network is an essential component of a distributed system or of a supercomputer based on large-sale parallel processing. Because in distributed systems the communication between processors is based on message exchange, the network topology is of a great importance. The interconnection network can be seen as a graph and the properties of a network can be studied using combinatorics and graph theory. A number of interconnection network topologies have been studied. The Extended Fibonacci Cube, EFC, is a topology which provides good properties for an interconnection network regarding diameter, node degree, recursive decomposition, embeddability and communication algorithms. In this research we present some properties of the Extended Fibonacci Cubes, we define a Gray code for extended Fibonacci cubes and show how a hamiltonian path, a hamiltonian cycle and a 2D mesh can be embedded in an Extended Fibonacci Cube.

Download

Keywords

  • Interconnection network
  • extended Fibonacci cube
  • embeddings
  • Gray code
  • hamiltonian path