圖的代數連通度

李菁

摘 要：本文證明了圖的代數連通度的一個新的上界，且此上界與圖的直徑和最大度有關。

關鍵詞：代數連通度；直徑；最大度

一、引言

設圖的頂點集表示由個頂點所構成的集合，即，表示圖的邊集。為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.

（作者單位：華南理工大學廣州學院計算機工程學院）