Journal
INFORMATION SCIENCES
Volume 180, Issue 15, Pages 2904-2914Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2010.04.003
Keywords
Bipancyclicity; Folded hypercubes; Fault-tolerant cycle embedding; Graph-theoretic interconnection networks; Hamiltonian cycles; Pancyclicity
Categories
Ask authors/readers for more resources
A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network's topology can simulate rings of various lengths. An n-dimensional folded hypercube FQ(n) is an attractive variant of an n-dimensional hypercube Q(n) that is obtained by establishing some extra edges between the vertices of Q(n). FQ(n) for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQ(n). For any FQ(n) (n >= 2) with at most 2n - 3 faulty edges, where each vertex is incident to 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, we prove 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 faulty edges tolerated. (C) 2010 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available