An Augmented Pancyclicity Problem of Crossed Cubes. (7th April 2017) - Chen, Hon-Chan; Kung, Tzu-Liang; Hsu, Lih-Hsing
Abstract: A graph G is pancyclic if it contains a cycle C of every length with 3 ≤ l ( C ) ≤ ∣ V ( G ) ∣, where l ( C ) denotes the length of C and ∣ V ( G ) ∣ denotes the number of vertices in G . In this paper, we propose an augmented pancyclicity problem for the n -dimensional crossed cube CQ n, which is a popular variant of the hypercube network. Let d C ( u, v ) denote the distance between any two distinct vertices u and v traversed by a cycle C in CQ n, n ≥ 4 . Then, for any integer m with ⌈ n + 1 2 ⌉ + 1 ≤ m ≤ 2 n − 1, there exist cycles C of various lengths in CQ n such that d C ( u, v ) = m, where (i) 2 m + 1 ≤ l ( C ) ≤ 2 n if n is odd and m = ⌈ n + 1 2 ⌉ + 1 and (ii) 2 m ≤ l ( C ) ≤ 2 n otherwise. This result indicates that any two distinct vertices of crossed cubes can be embedded on cycles of various feasible lengths with keeping any feasible distance from each other.