Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges

Sun Yuan Hsieh; Nai Wen Chang

doi:10.1109/TC.2006.104

Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges

Sun Yuan Hsieh, Nai Wen Chang

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

64 Citations (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 _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. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to V - F_v . 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
Pages (from-to)	854-863
Number of pages	10
Journal	IEEE Transactions on Computers
Volume	55
Issue number	7
DOIs	https://doi.org/10.1109/TC.2006.104
Publication status	Published - 2006 Jul

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Access to Document

10.1109/TC.2006.104

Cite this

@article{355390497dad4e88ac63d17f87450812,

title = "Hamiltonian path embedding and pancyclicity on the M{\"o}bius cube with 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 e be the sets of faulty nodes and faulty edges of an n-dimensional M{\"o}bius cube MQn, respectively, and let F = Fv ∪ Fe. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to V - Fv . 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 = "2006",

month = jul,

doi = "10.1109/TC.2006.104",

language = "English",

volume = "55",

pages = "854--863",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "7",

}

TY - JOUR

T1 - Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges

AU - Hsieh, Sun Yuan

AU - Chang, Nai Wen

PY - 2006/7

Y1 - 2006/7

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 e be the sets of faulty nodes and faulty edges of an n-dimensional Möbius cube MQn, respectively, and let F = Fv ∪ Fe. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to V - Fv . 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 e be the sets of faulty nodes and faulty edges of an n-dimensional Möbius cube MQn, respectively, and let F = Fv ∪ Fe. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to V - Fv . 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=33744794058&partnerID=8YFLogxK

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

U2 - 10.1109/TC.2006.104

DO - 10.1109/TC.2006.104

M3 - Article

AN - SCOPUS:33744794058

SN - 0018-9340

VL - 55

SP - 854

EP - 863

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 7

ER -

Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this