MPI-I-91-122

We prove several exact results for the dilation of well-known interconnection networks in cycles, namely : ${\rm dil}(T_{t,r},C_{(t^{r-1}-1)/(r-1)})=\lceil t(t^{r-1}-1)/(2(r-1)(t-1))\rceil,$ for complete $r$-level $t$-ary trees, ${\rm dil}(Q_n,C_{2^n}) =\sum_{k=0}^{n-1}{k\choose \lfloor \frac{k}{2}\rfloor },$ for $n$-dimensional hypercubes, ${\rm dil}(P_n\times P_n\times P_n,C_{n^3})= \lfloor 3n^2/4+n/2\rfloor,$ for 3-dimensional meshes (where $P_n$ is an $n$-vertex path) and ${\rm dil}(P_m\times P_n,C_{mn})= {\rm dil}(C_m\times P_n,C_{mn})={\rm dil}(C_m\times C_n,C_{mn})=\min\{m,n\},$ for 2-dimensional ordinary, cylindrical and toroidal meshes, respectively. The last results solve three remaining open problems of the type $"{\rm dil}(X\times Y, Z)=?"$, where $X,\ Y$ and $Z$ are paths or cycles. The previously known dilations are: ${\rm dil}(P_m\times P_n,P_{mn})= \min \{m,n\}$, ${\rm dil}(C_m\times P_n,P_{mn})=\min \{m,2n\}$ and ${\rm dil}(C_m\times C_n,P_{mn}) =2\min \{m,n\}$, if $m\neq n$, otherwise ${\rm dil}(C_n\times C_n)=2n-1$ . The proofs of the above stated results are based on the following technique. We find a suficient condition for a graph $G$ which assures the equality ${\rm dil}(G,C_n)={\rm dil}(G,P_n)$. We prove that trees, X-trees, meshes, hypercubes, pyramides and tree of meshes satisfy the condition. Using known optimal dilations of complete trees, hypercubes and 2- and 3-dimensional meshes in path we get the above exact result.