Embedding spanning disjoint cycles in augmented cube networks with prescribed vertices in each cycle

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 fork prescribed vertices x(1) ,x(2) , ... ,x(k) , there exist k disjoint cycles C-1 , C-2 , ... , C-k such that the union of C-1 , C-2 , ... , C-k spans G , and each C(j )contains exactly one vertex xj of x(1) , x(2 ), . .. ,x(k). 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 hyper cube Qn. In this paper, we prove that AQ(n) with n = 3 is spanning k-cyclable for 1 = k = 2n -4.