Edge-fault-tolerant pancyclicity of arrangement graphs

Sainan Sun; Min Xu; Kaishun Wang

doi:10.1016/j.ins.2014.06.046

Edge-fault-tolerant pancyclicity of arrangement graphs

Sainan Sun, Min Xu^*, Kaishun Wang

^*Corresponding author for this work

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

10 Citations (Scopus)

Abstract

The arrangement graph A_n,k is a well-known interconnection network. Day and Tripathi proved that A_n,k is pancyclic for n - k ≥ 2. In this paper, we improve this result, and we demonstrate that A_n,k is also pancyclic even if it has no more than (k(n - k) - 2) faulty edges for n - k ≥ 2. Our result is optimal concerning the edge fault-tolerance.

Original language	English
Pages (from-to)	50-62
Number of pages	13
Journal	Information Sciences
Volume	285
Issue number	1
Early online date	9 Jul 2014
DOIs	https://doi.org/10.1016/j.ins.2014.06.046
Publication status	Published - 20 Nov 2014
Externally published	Yes

Keywords

Arrangement graph
Edge-fault-tolerance
Hamiltonian
Hamiltonian connected
Pancyclicity

Access to Document

10.1016/j.ins.2014.06.046

Cite this

@article{19877a4f3614495693d62fc441588e80,

title = "Edge-fault-tolerant pancyclicity of arrangement graphs",

abstract = "The arrangement graph An,k is a well-known interconnection network. Day and Tripathi proved that An,k is pancyclic for n - k ≥ 2. In this paper, we improve this result, and we demonstrate that An,k is also pancyclic even if it has no more than (k(n - k) - 2) faulty edges for n - k ≥ 2. Our result is optimal concerning the edge fault-tolerance.",

keywords = "Arrangement graph, Edge-fault-tolerance, Hamiltonian, Hamiltonian connected, Pancyclicity",

author = "Sainan Sun and Min Xu and Kaishun Wang",

note = "Funding Information: This research is supported by NSFC (Nos. 11271047 and 61373021 ), the Fundation of “The study of fault diagnosis and reliability analysis in networks”, the Fundamental Research Funds for the Central University of China, and priority discipline of Beijing Normal University. ",

year = "2014",

month = nov,

day = "20",

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

language = "English",

volume = "285",

pages = "50--62",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Edge-fault-tolerant pancyclicity of arrangement graphs

AU - Sun, Sainan

AU - Xu, Min

AU - Wang, Kaishun

N1 - Funding Information: This research is supported by NSFC (Nos. 11271047 and 61373021 ), the Fundation of “The study of fault diagnosis and reliability analysis in networks”, the Fundamental Research Funds for the Central University of China, and priority discipline of Beijing Normal University.

PY - 2014/11/20

Y1 - 2014/11/20

N2 - The arrangement graph An,k is a well-known interconnection network. Day and Tripathi proved that An,k is pancyclic for n - k ≥ 2. In this paper, we improve this result, and we demonstrate that An,k is also pancyclic even if it has no more than (k(n - k) - 2) faulty edges for n - k ≥ 2. Our result is optimal concerning the edge fault-tolerance.

AB - The arrangement graph An,k is a well-known interconnection network. Day and Tripathi proved that An,k is pancyclic for n - k ≥ 2. In this paper, we improve this result, and we demonstrate that An,k is also pancyclic even if it has no more than (k(n - k) - 2) faulty edges for n - k ≥ 2. Our result is optimal concerning the edge fault-tolerance.

KW - Arrangement graph

KW - Edge-fault-tolerance

KW - Hamiltonian

KW - Hamiltonian connected

KW - Pancyclicity

UR - https://www.scopus.com/pages/publications/84961287963

U2 - 10.1016/j.ins.2014.06.046

DO - 10.1016/j.ins.2014.06.046

M3 - Article

AN - SCOPUS:84961287963

SN - 0020-0255

VL - 285

SP - 50

EP - 62

JO - Information Sciences

JF - Information Sciences

IS - 1

ER -

Edge-fault-tolerant pancyclicity of arrangement graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this