Laplace eigenvalues and bandwidth‐type invariants of graphs

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min‐sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min‐sums of random graphs, random regular graphs, and Kneser graphs.