Old and new results on algebraic connectivity of graphs
Old and new results on algebraic connectivity of graphs
复制标题
DOI：
10.1016/j.laa.2006.08.017
复制
发表时间：
2007-05-01
影响因子：
1.1
通讯作者：
de Abreu, Nair Maria Maia
中科院分区：
文献类型：
--
作者：
de Abreu, Nair Maria Maia
本文对图 G 的拉普拉斯算子的第二小特征值进行了调查，最著名的是 G 的代数连通性，表示为 a (G)。重点是作为其他图不变量的函数的代数连通性界限的分类，以及 Fiedler 向量（与 a(G) 相关的特征向量）在树上的应用，解决图中的难题以及组合优化问题。此外，还描述了a(G)的极限点和a(G)的极值图的表征，特别是那些代数连通性等于顶点连通性的图。 (C) 2006 Elsevier Inc. 保留所有权利。
This paper is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a (G). Emphasis is given on classifications of bounds to algebraic connectivity as a function of other graph invariants, as well as the applications of Fiedler vectors (eigenvectors realated to a(G)) on trees, oil hard problems in graphs and also oil the combinatorial optimization problems. Besides, limit points to a(G) and characterizations of extremal graphs to a(G) are described, especially those for which the algebraic connectivity is equal to the vertex connectivity. (C) 2006 Elsevier Inc. All rights reserved.