An Augmented Pancyclicity Problem of Crossed Cubes
Hon-Chan Chen, Tzu-Liang Kung, Lih‐Hsing Hsu · The Computer Journal · 2017
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 CQn, which is a popular variant of the hypercube network. Let dC(u,v) denote the distance between any two distinct vertices u and v traversed by a cycle C in CQn, n≥4. Then, for any integer m with ⌈n+12⌉+1≤m≤2n−1, there exist cycles C of various lengths in CQn such that dC(u,v)=m, where (i) 2m+1≤l(C)≤2n if n is odd and m=⌈n+12⌉+1 and (ii) 2m≤l(C)≤2n 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.