图的代数连通度

作者：李菁

来源：《亚太教育》2016年第14期

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

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

        一、引言

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

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

        二、相关结论

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

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

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

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

        通过计算可得，其中，。

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

图的代数连通度