Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges

Sun Yuan Hsieh, Pei Yu Yu

Research output: Contribution to journalArticle

23 Citations (Scopus)

Abstract

Two Hamiltonian paths are said to be fully independent if the ith vertices of both paths are distinct for all i between 1 and n, where n is the number of vertices of the given graph. Hamiltonian paths in a set are said to be mutually fully independent if two arbitrary Hamiltonian paths in the set are fully independent. On the other hand, two Hamiltonian cycles are independent starting at v if both cycles start at a common vertex v and the ith vertices of both cycles are distinct for all i between 2 and n. Hamiltonian cycles in a set are said to be mutually independent starting at v if any two different cycles in the set are independent starting at v. The n-dimensional hypercube is widely used as the architecture for parallel machines. In this paper, we study its fault-tolerant property and show that an n-dimensional hypercube with at most n-2 faulty edges can embed a set of fault-free mutually fully independent Hamiltonian paths between two adjacent vertices, and can embed a set of fault-free mutually independent Hamiltonian cycles starting at a given vertex. The number of tolerable faulty edges is optimal with respect to a worst case.

Original languageEnglish
Pages (from-to)153-162
Number of pages10
JournalJournal of Combinatorial Optimization
Volume13
Issue number2
DOIs
Publication statusPublished - 2007 Feb 1

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges'. Together they form a unique fingerprint.

  • Cite this