仅有三个悬挂点的图的补图的最小特征值

冯小芸，陈 旭，王国平

(新疆师范大学数学科学学院，乌鲁木齐 830017)

迄今为止，连通图的最小特征值已被广泛研究，Xing等[1]在给定固定点数和悬挂点数的所有cacti图中刻画了具有最小特征值的唯一图.Liu等[2]在具有固定悬挂点数的所有双圈图中给出了最小特征值达到最小值时的图.Wang等[3]在带有割边的所有图中，确定了最小特征值达到最小值时的图.Liu等[4]确定了含有k个悬挂点的n个点的单圈图的最小特征值.

图G=(V(G)，E(G))的补图记为Gc=(V(Gc)，E(Gc))，其中V(Gc)=V(G)且E(Gc)={xy：x，y∈V(G)，xy∉E(G)}.近几年，特殊图类的补图的最小特征值及相关问题引起了不少人的关注，Ren等[5]确定了一类θ图的补图的色等价类.Favaron等[6]得到了图及其补图的总控制权和总控制权细分数.Ando等[7]讨论了3连通图的补图的联通度.Fan等[8]给出了所有树的补图中最小特征值达到极小时的连通图，Jiang等[9]得到了恰有两个悬挂点的图的所有连通补图的最小特征值.

本文在仅有三个悬挂点的图的所有连通补图中，确定了其最小特征值达到最小值时的唯一图.

1 主要引理及证明

假定G是点集为V(G)={v1，v2，…，vn}的一个图，且令X=(Xv1，Xv2，…，Xvn)T是使得Xvi=X(vi)(1≤i≤n)的一个单位向量，因此，

(1)

若X≠0是与G的特征值λ(G)对应的一个特征向量，则任意的vi∈V(G)都有

(2)

其中，NG(vi)是点Vi的邻域，等式(2)称为G的特征方程.

令Kn是n个点的完全图，若G是至少含有一条边的连通图，则K2是G的一个诱导子图，已知λn(K2)=-1，由交错定理知λn(G)≤-1.

再次，通过特征方程(2)，有

通过以上方程和特征方程(2)，对任意的v′∈NG(u){w}，得到

前面提到λn(Gc)<-1，结合以上方程可以得到Xv′=Xw>0，该矛盾表明X至少包含两个正分量.由于-X也是Gc的最小特征向量……