Abstract
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.
