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

Sun Yuan Hsieh; Nai Wen Chang

doi:10.1109/ICPADS.2005.119

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

Sun Yuan Hsieh, Nai Wen Chang

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 F_v and F_e be the sets of faulty nodes and faulty edges of an n-dimensional Möbius cube MQ_n, respectively, and let F = F_v ∪ F_e. In this paper, we show that MQ_n - F contains a fault-free Hamiltonian path when |F| ≤ n -1 and n ≥ 1. We also show that MQ_n -F is pancyclic when |F| ≤ n - 2 and n ≥ 2. Since MQ_n is regular of degree n, both results are optimal in the worst case.

Original language	English
Title of host publication	Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
Editors	J. Ma, L.T. Yang
Pages	620-624
Number of pages	5
DOIs	https://doi.org/10.1109/ICPADS.2005.119
Publication status	Published - 2005 Sep 1
Event	11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005 - Fukuoka, Japan Duration: 2005 Jul 20 → 2005 Jul 22

Publication series

Name	Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume	2
ISSN (Print)	1521-9097

Other

Other	11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
Country	Japan
City	Fukuoka
Period	05-07-20 → 05-07-22

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Access to Document

10.1109/ICPADS.2005.119

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

@inproceedings{9d66d18eac404123b8381073d235b89b,

title = "Cycle embedding on the M{\"o}bius cube with both faulty nodes and faulty edges",

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{\"o}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.",

author = "Hsieh, {Sun Yuan} and Chang, {Nai Wen}",

year = "2005",

month = sep,

day = "1",

doi = "10.1109/ICPADS.2005.119",

language = "English",

isbn = "0769522815",

series = "Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS",

pages = "620--624",

editor = "J. Ma and L.T. Yang",

booktitle = "Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005",

note = "11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005 ; Conference date: 20-07-2005 Through 22-07-2005",

}

Hsieh, SY & Chang, NW 2005, Cycle embedding on the Möbius cube with both faulty nodes and faulty edges. in J Ma & LT Yang (eds), Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005. Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS, vol. 2, pp. 620-624, 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005, Fukuoka, Japan, 05-07-20. https://doi.org/10.1109/ICPADS.2005.119

Cycle embedding on the Möbius cube with both faulty nodes and faulty edges. / Hsieh, Sun Yuan ; Chang, Nai Wen.

Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005. ed. / J. Ma; L.T. Yang. 2005. p. 620-624 (Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Hsieh, Sun Yuan

AU - Chang, Nai Wen

PY - 2005/9/1

Y1 - 2005/9/1

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

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

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

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

U2 - 10.1109/ICPADS.2005.119

DO - 10.1109/ICPADS.2005.119

M3 - Conference contribution

AN - SCOPUS:23944486716

SN - 0769522815

T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS

SP - 620

EP - 624

BT - Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005

A2 - Ma, J.

A2 - Yang, L.T.

T2 - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005

Y2 - 20 July 2005 through 22 July 2005

ER -

Hsieh SY , Chang NW. Cycle embedding on the Möbius cube with both faulty nodes and faulty edges. In Ma J, Yang LT, editors, Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005. 2005. p. 620-624. (Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS). https://doi.org/10.1109/ICPADS.2005.119