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 - http://www.scopus.com/inward/record.url?scp=84961287963&partnerID=8YFLogxK
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 -