# MPI-I-91-122

## On embeddings in cycles

### Hromkovic, Juraj and Müller, Vladimír and Sýkora, Ondrej and Vrto, Imrich

**MPI-I-91-122**. November** **1991, 22 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

91-122.pdf | 26716 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-122

**BibTeX**
`@TECHREPORT{``HromkovicMuellerSykoraVrto91``,`

` AUTHOR = {Hromkovic, Juraj and M{\"u}ller, Vladim{\'i}r and Sýkora, Ondrej and Vrto, Imrich},`

` TITLE = {On embeddings in cycles},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-91-122},`

` MONTH = {November},`

` YEAR = {1991},`

` ISSN = {0946-011X},`

`}`