TY - GEN

T1 - Fault-free cycles in conditional faulty folded hypercubes

AU - Kuo, Che Nan

AU - Hsieh, Sun Yuan

PY - 2009

Y1 - 2009

N2 - An n-dimensional folded hypercube FQ n is an attractive variance of an n-dimensional hypercube Q n , which is obtained by a standard hypercube with some extra edges established between its vertices. FQ n for any odd n is known to be bipartite. In this paper, for any FQ n (n > 2) with at most 2n-3 faulty edges in which each vertex is incident with at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2 n , and when n > 2 is even, there also exists a fault-free cycle of every odd length from n + 1 to 2 n - 1. The result is optimal with respect to the number of edges faults tolerated.

AB - An n-dimensional folded hypercube FQ n is an attractive variance of an n-dimensional hypercube Q n , which is obtained by a standard hypercube with some extra edges established between its vertices. FQ n for any odd n is known to be bipartite. In this paper, for any FQ n (n > 2) with at most 2n-3 faulty edges in which each vertex is incident with at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2 n , and when n > 2 is even, there also exists a fault-free cycle of every odd length from n + 1 to 2 n - 1. The result is optimal with respect to the number of edges faults tolerated.

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

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

U2 - 10.1007/978-3-642-03095-6_42

DO - 10.1007/978-3-642-03095-6_42

M3 - Conference contribution

AN - SCOPUS:70349109272

SN - 3642030947

SN - 9783642030949

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 439

EP - 448

BT - Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings

T2 - 9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009

Y2 - 8 June 2009 through 11 June 2009

ER -