Bandwidth of the product of paths of the same length

Abstract: In this note we give a numerical expression for the bandwidth

b w (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

b w (P_{n}^{d})

is bounded above and below by the largest coefficient in the expansion of

(1 + x + ... + x^{n})^{k}

, with

k i n d, d + 1

. Moreover, we compare the asymptotic behavior of

b w (P_{n}^{d})

with the bandwidth of the labeling obtained by ordering the vertices of

P_{n}^{d}

in lexicographic order.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Bandwidth of the product of paths of the same length