An Augmented Pancyclicity Problem of Crossed Cubes. (7th April 2017)

• Record Type: Journal Article
• Authors: Chen, Hon-Chan; Kung, Tzu-Liang; Hsu, Lih-Hsing
• Is Part Of: Computer journal. Volume 61:Number 1(2018)
• Page Start: 54
• Page End: 62
• Publication Date: 2017-04-07
• Subjects: interconnection network -- crossed cube -- cycle embedding -- distance; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx034
• Languages: English
• ISSNs: 0010-4620

Abstract

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.