In this paper, we consider two embedding problems in Cartesian product networks: one is the pancycle problem, which involves embedding cycles of various lengths in the given product network; and the other is the panconnectivity problem, which involves embedding paths of various lengths between any pair of distinct nodes in the given product network. We then apply our technical lemmas and theorems to derive new topological properties of two multiprocessor systems, namely, generalized hypercubes and nearest neighbor mesh hypercubes.

Given a nonnegative integer r, a no-hole (r+1)-distant coloring, called $\hbox{N}_{r}$-coloring, of a graph G is a function that assigns a nonnegative integer (color) to each vertex such that the separation of the colors of any pair of adjacent vertices is greater than r,, and the set of the colors used must be consecutive. Given r and G, the minimum N r -span of G, nsp r (G), is the minimum difference of the largest and the smallest colors used in an N r -coloring of G if there exists one; otherwise, define ${\rm nsp}_r(G)=\infty$. The values of nsp 1 (G) (r=1) for bipartite graphs are given by Roberts [Math. Comput. Modelling, 17 (1993), pp. 139--144]. Given $r \geq 2$, we determine the values of nsp r (G) for all bipartite graph with at least r-2 isolated vertices. This leads to complete solutions of nsp 2 (G) for bipartite graphs.