Pancyclicity and bipancyclicity of conditional faulty folded hypercubes ?
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 networks topology can simulate rings of various lengths. An n-dimensional folded hypercube FQn is an attractive variant of an n-dimensional hypercube Qn that is obtained by establishing some extra edges between the vertices of Qn. FQn for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQn. For any FQn (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 2n; and when n?2 is even, we prove there also exists a fault-free cycle of every odd length from n+1 to 2n?1. The result is optimal with respect to the number of faulty edges tolerated.
pancyclicity bipancyclicity folded hypercubes fault-tolerant cycle embedding graph-theoretic interconnection networks hamiltonian cycles