Pancyclicity on Möbius cubes with edge faults

Sun Yuan Hsieh; Chun Hua Chen

Pancyclicity on Möbius cubes with edge faults

Department of Computer Science and Information Engineering

Research output: Contribution to conference › Paper › peer-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 F_e 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 |F_e| ≤ 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 language	English
Pages	168-173
Number of pages	6
Publication status	Published - 2004 Aug 16
Event	Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN - Hong Kong, China Duration: 2004 May 10 → 2004 May 12

Other

Other	Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
Country/Territory	China
City	Hong Kong
Period	04-05-10 → 04-05-12

All Science Journal Classification (ASJC) codes

Computer Science(all)

Cite this

@conference{504debd870ea41f3a82dc1000e65bcc2,

title = "Pancyclicity on M{\"o}bius cubes with edge faults",

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{\"o}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{\"o}bius cube is regular of degree n, both results are optimal in the worst case.",

author = "Hsieh, {Sun Yuan} and Chen, {Chun Hua}",

year = "2004",

month = aug,

day = "16",

language = "English",

pages = "168--173",

note = "Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN ; Conference date: 10-05-2004 Through 12-05-2004",

}

TY - CONF

T1 - Pancyclicity on Möbius cubes with edge faults

AU - Hsieh, Sun Yuan

AU - Chen, Chun Hua

PY - 2004/8/16

Y1 - 2004/8/16

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=3543138427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3543138427&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:3543138427

SP - 168

EP - 173

T2 - Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN

Y2 - 10 May 2004 through 12 May 2004

ER -

Pancyclicity on Möbius cubes with edge faults

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this