History

Please fill in your query. A complete syntax description you will find on the General Help page.
Hamiltonian paths and cycles with prescribed edges in the 3-ary $n$-cube. (English)
Inf. Sci. 181, No. 14, 3054-3065 (2011).
Summary: The $k$-ary $n$-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set $\cal P$ of at most $2n - 2$ $(n \geqslant 2)$ prescribed edges and two vertices $u$ and $v$, we show that the 3-ary $n$-cube contains a Hamiltonian path between $u$ and $v$ passing through all edges of $\cal P$ if and only if the subgraph induced by $\cal P$ consists of pairwise vertex-disjoint paths, none of them having $u$ or $v$ as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary $n$-cube contains a Hamiltonian cycle passing through a set $\cal P$ of at most $2n - 1$ prescribed edges if and only if the subgraph induced by $\cal P$ consists of pairwise vertex-disjoint paths.