Pancyclicity on Möbius cubes with edge faults

Sun Yuan Hsieh, Chun Hua Chen

Research output: Contribution to conferencePaperpeer-review

Abstract

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

Original languageEnglish
Pages168-173
Number of pages6
Publication statusPublished - 2004 Aug 16
EventProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN - Hong Kong, China
Duration: 2004 May 102004 May 12

Other

OtherProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
CountryChina
CityHong Kong
Period04-05-1004-05-12

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Pancyclicity on Möbius cubes with edge faults'. Together they form a unique fingerprint.

Cite this