BOUNDS FOR THE BANDWIDTH OF THE d-ARY DE BRUIJN GRAPH

Publisher Website
Google Scholar
Abstract
The computation of upper bounds of the bandwidth of graphs is mainly based on the giving of a numbering which achieves these bounds. In [9], Harper proposed such a numbering for the binary hypercube, based on the Hamming weights and binary values of the hypercube vertices. By defining an extended Hamming weight, this numbering can lead to an equivalent proof for the d-ary de Bruijn graph. We present in this paper an approach, based on the use of the continuous domain and Laplace’s theorem for asymptotically evaluating integrals, which leads to the enumeration of the vertices of the same extended Hamming weight in the non-binary case. This result allows the computation of an upper bound of the bandwidth of the unoriented de Bruijn graph, as well as an upper bound of its vertex-bisection when both the diameter and the degree are even.

This publication has 0 references indexed in Scilit: