The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian
The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian
复制标题
限制拉普拉斯最小非平凡特征值的路径阻力法
DOI：
10.1017/s0963548399003958
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
G. Miller
中科院分区：
文献类型：
--
作者：
Stephen Guattery;F. Leighton;G. Miller
引入了求解图的拉普拉斯矩阵最小非平凡特征值下界的路径阻力法。该方法基于从电路的角度来看待图，当Dirichlet边界条件为零时，用团嵌入来产生λ2的下界，用星形嵌入来产生最小瑞利商的下界。该方法为嵌入中的路径分配优先级；我们证明，对于一个未加权的树T，使用统一优先级的团嵌入在λ2上产生一个下界，该下界最多偏离O（log diameter(T)）因子。我们证明了这种方法可以为团嵌入产生的最佳边界与使用团嵌入和边长度产生边界的相关方法相同。
We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical circuits: it uses clique embeddings to produce lower bounds on λ2 and star embeddings to produce lower bounds on the smallest Rayleigh quotient when there is a zero Dirichlet boundary condition. The method assigns priorities to the paths in the embedding; we show that, for an unweighted tree T, using uniform priorities for a clique embedding produces a lower bound on λ2 that is off by at most an O(log diameter(T)) factor. We show that the best bounds this method can produce for clique embeddings are the same as for a related method that uses clique embeddings and edge lengths to produce bounds.