Cycle embedding on the Möbius cube with both faulty nodes and faulty edges

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (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 Fe be the sets of faulty nodes and faulty edges of an n-dimensional Möbius cube MQn, respectively, and let F = Fv ∪ Fe. 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
Title of host publicationProceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
EditorsJ. Ma, L.T. Yang
Pages620-624
Number of pages5
DOIs
Publication statusPublished - 2005 Sep 1
Event11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005 - Fukuoka, Japan
Duration: 2005 Jul 202005 Jul 22

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume2
ISSN (Print)1521-9097

Other

Other11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
CountryJapan
CityFukuoka
Period05-07-2005-07-22

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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

  • Cite this

    Hsieh, S. Y., & Chang, N. W. (2005). Cycle embedding on the Möbius cube with both faulty nodes and faulty edges. In J. Ma, & L. T. Yang (Eds.), Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005 (pp. 620-624). (Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS; Vol. 2). https://doi.org/10.1109/ICPADS.2005.119