Bandwidth of the product of paths of the same length

preprint2012arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.