Narrow Results

An important tool for the execution of parallel algorithms and the simulation of interconnection networks is graph embedding. The quality of an embedding can be assessed using some cost metrics. The dilation and wirelength are the commonly used parameters. The Knödel graph $W_{\mathrm{\Delta },n}$ is a minimum linear gossip network and has minimum broadcasting. It has $n$ vertices, $\frac{n\mathrm{\Delta }}{2}$ edges, where $n$ is even, and $1\le \mathrm{\Delta }\le \lfloor$log${}_{2}n\rfloor$. In this study, we solve the dilation problem of embedding the Knödel graph into certain cube-like architectures such as hypercube, folded hypercube, and augmented cube. In [G. Fertin, A. Raspaud, A survey on Knödel graphs, Discrete Applied Mathematics 137 (2004) 173–195], it is proved that the dilation of embedding the Knödel graph $W_{\mathrm{\Delta },2^{\mathrm{\Delta }}}$ into the hypercube $Q_{\mathrm{\Delta }}$ is at most $4$. In this study, we obtain an improved upper bound for dilation of embedding the Knödel graph into the hypercube and it is equal to $3$. Also, we calculate the wirelength of embedding the Knödel graph into the above-said cube-like architectures using dilation.