Conditional edge-fault Hamiltonicity of augmented cubes

Sun Yuan Hsieh; Yi Ru Cian

doi:10.1016/j.ins.2010.03.005

Conditional edge-fault Hamiltonicity of augmented cubes

Sun Yuan Hsieh, Yi Ru Cian

Department of Computer Science and Information Engineering

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

45 Citations (Scopus)

Abstract

The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n ≥ 3) with faulty edges up to 4 n - 8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated.

Original language	English
Pages (from-to)	2596-2617
Number of pages	22
Journal	Information sciences
Volume	180
Issue number	13
DOIs	https://doi.org/10.1016/j.ins.2010.03.005
Publication status	Published - 2010 Jul 1

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Theoretical Computer Science
Computer Science Applications
Information Systems and Management
Artificial Intelligence

Access to Document

10.1016/j.ins.2010.03.005

Cite this

@article{7b09a990e7744522b103710f0e54220e,

title = "Conditional edge-fault Hamiltonicity of augmented cubes",

abstract = "The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n ≥ 3) with faulty edges up to 4 n - 8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated.",

author = "Hsieh, {Sun Yuan} and Cian, {Yi Ru}",

year = "2010",

month = jul,

day = "1",

doi = "10.1016/j.ins.2010.03.005",

language = "English",

volume = "180",

pages = "2596--2617",

journal = "Information sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

number = "13",

}

TY - JOUR

T1 - Conditional edge-fault Hamiltonicity of augmented cubes

AU - Hsieh, Sun Yuan

AU - Cian, Yi Ru

PY - 2010/7/1

Y1 - 2010/7/1

N2 - The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n ≥ 3) with faulty edges up to 4 n - 8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated.

AB - The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n ≥ 3) with faulty edges up to 4 n - 8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated.

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

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

U2 - 10.1016/j.ins.2010.03.005

DO - 10.1016/j.ins.2010.03.005

M3 - Article

AN - SCOPUS:77950864654

SN - 0020-0255

VL - 180

SP - 2596

EP - 2617

JO - Information sciences

JF - Information sciences

IS - 13

ER -

Conditional edge-fault Hamiltonicity of augmented cubes

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this