Premium
Laplace eigenvalues and bandwidth‐type invariants of graphs
Author(s) -
Juvan Martin,
Mohar Bojan
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170313
Subject(s) - mathematics , eigenvalues and eigenvectors , combinatorics , laplacian matrix , laplace operator , indifference graph , bandwidth (computing) , discrete mathematics , chordal graph , random graph , laplace transform , graph , mathematical analysis , computer science , computer network , physics , quantum mechanics
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. © John Wiley & Sons, Inc.