کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
394184 | 665782 | 2010 | 11 صفحه PDF | دانلود رایگان |
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 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.
Journal: Information Sciences - Volume 180, Issue 15, 1 August 2010, Pages 2904–2914