图的代数连通度

李菁

摘 要：本文证明了图的代数连通度的一个新的上界，且此上界与图的直径和最大度有关。

关键词：代数连通度；直径；最大度

一、引言

设图的顶点集表示由个顶点所构成的集合，即，表示图的边集。为Laplace矩阵任意一个特征值，为对应的特征向量。由文献[1]可知：。

文献[2]给出了部分结论：，其中，图有两条至少相距的边。文献[1]在更进一步的研究中把与直径关联，但文中在处理这问题的时候出现了错误，本文将会重新证明其结论。

二、相关结论

顶点的邻域记为，表示所有与顶点相邻的顶点的集合。即，为与顶点距离为1的所有顶点的集合。用集合表示与顶点距离为的所有顶点的集合。特别地，。表示实数取下整。若图中两个顶点集合和相连，则存在頂点和顶点，使得边；反之，则称集合和不相连。

定理：设为图的代数连通度，为图的直径，为图最大度，则

证明：图的直径记为，考虑图上的一条直径路的两个端点、，则这两个顶点的距离为。若直径为奇数，则设；若直径为偶数，则设。故有，。

是该直径的端点组成的集合，即；是该直径另一个端点组成的集合，即。（）是到顶点的距离为的所有顶点的集合，（）是到顶点的距离为的所有顶点的集合。从这些集合的构造可知，这些集合都是互不相交的，并且没有任何一条边连接两个集合和，即集合和不相连。对于，分别有以及成立。对于给定的，定义一个维向量，其中对应顶点的各分量为：若顶点，则；若顶点，则；否则，。通过调节的取值，可以满足（对于给定的图，与这两项均为定值，则不同的图可取不同的值，使得满足以上方程），即，可以使得向量与全1向量正交。由文献[2]知

通过计算可得，其中，。

对于任意的，都有，且集合与集合（）不相连，集合（）与集合也不相连。因此，，其中

由、的定义可知，，，故有，

三、结论

代数连通度是Laplace图谱的次小特征值，是研究图谱问题的重要指标。本文重新修正一篇关于图的代数连通度的上界的论文的证明过程，此上界可用图的直径和最大度进行估算。

参考文献：

[1]Newman M W.The Laplacian Spectrum of Graphs[D]，2000.

[2]Nilli A.On the second eigenvalue of a graph[J].Discrete Mathematics，1991（91）：207-210.

[3]：田贵贤，黄廷祝，崔淑玉.Bounds on the Algebraic Connectivity of Graphs[J].数学进展，2012，41（2）：217-224.

[4]周后卿，周琪.正则图的代数连通度[J].四川师范大学学报，2012，2（35）：219-221.

[5]Das K C.The Laplacian spectrum of a graph[J].Computers &；Mathematics with Applications，2004，48（5-6）：715-724.

（作者单位：华南理工大学广州学院计算机工程学院）