Bandwidth of the product of paths of the same length

Abstract

In this note we give a numerical expression for the bandwidth $bw(P_n^d)$ of the $d$-product of a path with $n$ edges, $P_n^d$. We prove that this bandwidth is given by the sum of certain multinomial coefficients. We also show that $bw(P_n^d)$ is bounded above and below by the largest coefficient in the expansion of $(1+x+...+x^n{)}^k$, with $k\in d,d+1$. Moreover, we compare the asymptotic behavior of $bw(P_n^d)$ with the bandwidth of the labeling obtained by ordering the vertices of $P_n^d$ in lexicographic order.

10 pages, 1 figure