Minimum Vertex Covers and the Spectrum of the Normalized Laplacian on Trees
Minimum Vertex Covers and the Spectrum of the Normalized Laplacian on Trees
复制标题
DOI：
10.1016/j.laa.2012.04.005
复制
发表时间：
2010-10
影响因子：
1.1
通讯作者：
Hao Chen;J. Jost
中科院分区：
文献类型：
--
作者：
Hao Chen;J. Jost
我们表明，在树上归一化图拉普拉斯算子的图谱中，特征值 1 和接近 1 的特征值与最小顶点覆盖密切相关。具体地，对于特征值1，其重数与最小顶点覆盖的大小有关，其特征向量的零项对应于最小顶点覆盖中的顶点；而对于接近 1 的特征值，可以根据最小顶点覆盖来估计它们到 1 的距离；对于小于1的最大特征值，其特征向量的符号图以最小顶点覆盖中的顶点为代表。
We show that, in the graph spectrum of the normalized graph Laplacian on trees, the eigenvalue 1 and eigenvalues near 1 are strongly related to minimum vertex covers. In particular, for the eigenvalue 1, its multiplicity is related to the size of a minimum vertex cover, and zero entries of its eigenvectors correspond to vertices in minimum vertex covers; while for eigenvalues near 1, their distance to 1 can be estimated from minimum vertex covers; and for the largest eigenvalue smaller than 1, the sign graphs of its eigenvectors take vertices in a minimum vertex cover as representatives.