关于代数连通度的一个注记

摘要

图G=(V E)的次小的拉普拉斯特征值称为G的代数连通度,记为α(G).设δ(G)为G的最小度.Fiedler早在1973年便证明了α(G)≤ δ(G),但他未能给出等号成立的极图刻划.后来,我们在[6]中确定了当δ(G)≤(1/2)|V(G)|时α(G)=δ(G)的充要条件.本文中,我们将确定任意情况下α(G)=δ(G)成立的所有极图.