李菁

摘 要：本文證明了圖的代數(shù)連通度的一個(gè)新的上界，且此上界與圖的直徑和最大度有關(guān)。

關(guān)鍵詞：代數(shù)連通度；直徑；最大度

一、引言

設(shè)圖的頂點(diǎn)集表示由個(gè)頂點(diǎn)所構(gòu)成的集合，即，表示圖的邊集。為L(zhǎng)aplace矩陣任意一個(gè)特征值，為對(duì)應(yīng)的特征向量。由文獻(xiàn)[1]可知：。

文獻(xiàn)[2]給出了部分結(jié)論：，其中，圖有兩條至少相距的邊。文獻(xiàn)[1]在更進(jìn)一步的研究中把與直徑關(guān)聯(lián)，但文中在處理這問(wèn)題的時(shí)候出現(xiàn)了錯(cuò)誤，本文將會(huì)重新證明其結(jié)論。

二、相關(guān)結(jié)論

頂點(diǎn)的鄰域記為，表示所有與頂點(diǎn)相鄰的頂點(diǎn)的集合。即，為與頂點(diǎn)距離為1的所有頂點(diǎn)的集合。用集合表示與頂點(diǎn)距離為的所有頂點(diǎn)的集合。特別地，。表示實(shí)數(shù)取下整。若圖中兩個(gè)頂點(diǎn)集合和相連，則存在頂點(diǎn)和頂點(diǎn)，使得邊；反之，則稱集合和不相連。

定理：設(shè)為圖的代數(shù)連通度，為圖的直徑，為圖最大度，則

證明：圖的直徑記為，考慮圖上的一條直徑路的兩個(gè)端點(diǎn)、，則這兩個(gè)頂點(diǎn)的距離為。若直徑為奇數(shù)，則設(shè)；若直徑為偶數(shù)，則設(shè)。故有，。

是該直徑的端點(diǎn)組成的集合，即；是該直徑另一個(gè)端點(diǎn)組成的集合，即。（）是到頂點(diǎn)的距離為的所有頂點(diǎn)的集合，（）是到頂點(diǎn)的距離為的所有頂點(diǎn)的集合。從這些集合的構(gòu)造可知，這些集合都是互不相交的，并且沒(méi)有任何一條邊連接兩個(gè)集合和，即集合和不相連。對(duì)于，分別有以及成立。對(duì)于給定的，定義一個(gè)維向量，其中對(duì)應(yīng)頂點(diǎn)的各分量為：若頂點(diǎn)，則；若頂點(diǎn)，則；否則，。通過(guò)調(diào)節(jié)的取值，可以滿足（對(duì)于給定的圖，與這兩項(xiàng)均為定值，則不同的圖可取不同的值，使得滿足以上方程），即，可以使得向量與全1向量正交。由文獻(xiàn)[2]知

通過(guò)計(jì)算可得，其中，。

對(duì)于任意的，都有，且集合與集合（）不相連，集合（）與集合也不相連。因此，，其中

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

三、結(jié)論

代數(shù)連通度是Laplace圖譜的次小特征值，是研究圖譜問(wèn)題的重要指標(biāo)。本文重新修正一篇關(guān)于圖的代數(shù)連通度的上界的論文的證明過(guò)程，此上界可用圖的直徑和最大度進(jìn)行估算。

參考文獻(xiàn)：

[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].數(shù)學(xué)進(jìn)展，2012，41（2）：217-224.

[4]周后卿，周琪.正則圖的代數(shù)連通度[J].四川師范大學(xué)學(xué)報(bào)，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.

（作者單位：華南理工大學(xué)廣州學(xué)院計(jì)算機(jī)工程學(xué)院）