Pancyclicity on Möbius cubes with edge faults

Sun Yuan Hsieh, Chun Hua Chen

研究成果: Paper

摘要

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.

原文English
頁面168-173
頁數6
出版狀態Published - 2004 八月 16
事件Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN - Hong Kong, China
持續時間: 2004 五月 102004 五月 12

Other

OtherProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
國家China
城市Hong Kong
期間04-05-1004-05-12

指紋

Hamiltonians

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

引用此文

Hsieh, S. Y., & Chen, C. H. (2004). Pancyclicity on Möbius cubes with edge faults. 168-173. 論文發表於 Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, Hong Kong, China.
Hsieh, Sun Yuan ; Chen, Chun Hua. / Pancyclicity on Möbius cubes with edge faults. 論文發表於 Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, Hong Kong, China.6 p.
@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 = "8",
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",

}

Hsieh, SY & Chen, CH 2004, 'Pancyclicity on Möbius cubes with edge faults', 論文發表於 Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, Hong Kong, China, 04-05-10 - 04-05-12 頁 168-173.

Pancyclicity on Möbius cubes with edge faults. / Hsieh, Sun Yuan; Chen, Chun Hua.

2004. 168-173 論文發表於 Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, Hong Kong, China.

研究成果: Paper

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

ER -

Hsieh SY, Chen CH. Pancyclicity on Möbius cubes with edge faults. 2004. 論文發表於 Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, Hong Kong, China.