Let $G$ and $H$ be graphs, with $|V(H)|\geq |V(G)| $, and $f:V(G)\rightarrow V(H)$ a one to one map of their vertices. Let $dilation(f) = max\{ dist_{ H}(f(x),f(y)): xy\in E(G) \}$, where $dist_{ H}(v,w)$ is the distance between vertices $v$ and $w$ of $H$. Now let $B(G,H)$ = $min_{ f}\{ dilation(f) \}$, over all such maps $f$. The parameter $B(G,H)$ is a generalization of the classic and well studied "bandwidth" of $G$, defined as $B(G,P(n))$, where $P(n)$ is the path on $n$ points and $n = |V(G)|$. Let $[a_{ 1}\times a_{ 2}\times \cdots \times a_{ k} ]$ be the $k$-dimensional grid graph with integer values $1$ through $a_{ i}$ in the $i$'th coordinate. In this paper, we study $B(G,H)$ in the case when $G = [a_{ 1}\times a_{ 2}\times \cdots \times a_{ k} ]$ and $H$ is the hypercube $Q_{ n}$ of dimension $n = \lceil log_{ 2}(|V(G)|) \rceil$, the hypercube of smallest dimension having at least as many points as $G$. Our main result is that $$B( [a_{ 1}\times a_{ 2}\times \cdots \times a_{ k} ],Q_{ n}) \le 3k,$$ provided $a_{ i} \geq 2^{ 22}$ for each $1\le i\le k$. For such $G$, the bound $3k$ improves on the previous best upper bound $4k+O(1)$. Our methods include an application of Knuth's result on two-way rounding and of the existence of spanning regular cyclic caterpillars in the hypercube.
Categories: math.CO