图的二维带宽及其Laplacian特征值

摘要

The 2-dimensional bandwidth problem may be stated as follows: Given a graph G, find an embedding of it in the grid graph, such that a certain function based on the chosen embedding will attain its optimal (usually minimum). In this paper we study the relationship between the 2-dimensional bandwidth and the Laplacian eigenvalues of a graph.%图的二维带宽问题是将图G嵌入平面网格图,并使基于该嵌入的函数取得最优值(通常是最小值).本文研究了图的二维带宽与其Laplacian特征值之间的关系.