Embedding spanning disjoint cycles in augmented cube networks with prescribed vertices in each cycle
Weiyan Wu, Eminjan Sabir, Hongwei Qiao · International Journal of Parallel Emergent and Distributed Systems · 2023
One of the important issues in evaluating an interconnection network is to study the Hamiltonian cycle embedding problems. For a positive integer k, a graph G is said to be spanning k-cyclable if for k prescribed vertices x1,x2,…,xk, there exist k disjoint cycles C1,C2,…,Ck such that the union of C1,C2,…,Ck spans G, and each Cj contains exactly one vertex xj of x1,x2,…,xk. According to the definition, the problem of finding hamiltonian cycle focuses on k = 1. The notion of spanning cyclability can be applied to the problem of identifying faulty processors and other related issues in interconnection networks. The n-dimensional augmented cube AQn is an important node-symmetric variant of the n-dimensional hypercube Qn. In this paper, we prove that AQn with n≥3 is spanning k-cyclable for 1≤k≤2n−4.