Panconnectivity and pancyclicity of the 3-ary n-cube network under the path restrictions

摘要

The k-ary n-cube, denoted by Qnk, is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding paths and cycles into 3-ary n-cubes under the path restrictions. Let P be a path in Qn3. We show that when |V(P)|⩽2n-3, there exists a path of any length from n+1 to |V(Qn3-P)|-1 between two arbitrary nodes in Qn3-P. We also prove that when |E(P)|⩽2n-1, there exists a cycle of any length from |E(P)|+n to |V(Qn3)| in Qn3 passing through P. Our results are best possible in some sense.