Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges

Research output: Contribution to journalArticlepeer-review

57 Citations (Scopus)

Abstract

A graph G = (V,E) is said to be pancyclic if it contains fault-free cycles of all lengths from 4 to V in G. Let Fv and e be the sets of faulty nodes and faulty edges of an n-dimensional Möbius cube MQn, respectively, and let F = Fv ∪ Fe. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to V - Fv . In this paper, we show that MQn - F contains a fault-free Hamiltonian path when F ≤ n - 1 and n ≥ 1. We also show that MQn - F is pancyclic when F ≤ n - 2 and n ≥ 2. Since MQn is regular of degree n, both results are optimal in the worst case.

Original languageEnglish
Pages (from-to)854-863
Number of pages10
JournalIEEE Transactions on Computers
Volume55
Issue number7
DOIs
Publication statusPublished - 2006 Jul 1

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges'. Together they form a unique fingerprint.

Cite this