支配数为1的图的最小特征值

查淑萍，吴　琼

(安庆师范学院 数学与计算科学学院，安徽 安庆 246133)



支配数为1的图的最小特征值

查淑萍，吴琼

(安庆师范学院 数学与计算科学学院，安徽 安庆 246133)

摘要：本文中主要刻画了给定阶数且支配数为1的图类中最小特征值达到极小的图的结构。

关键词：图; 邻接矩阵; 最小特征值; 支配数

图G的一个支配集是图G的顶点集V(G)的一个子集X，使得对V(G)-X中的任一顶点至少与X中的一个顶点相邻,其中顶点数最少的支配集称为图G的最小支配集，而最小支配集中所含的顶点数称为图G的支配数。

关于图的谱半径，已经有了很多的研究结果，而近年来，有很多研究者也在关注图的最小特征值的研究，尤其是刻画某图类中的极小图，如Bell[1,2]等刻画了给定边数的图中的极小图,Fan等[3]刻画了给定围长的单圈图中的极小图，Liu[4]等讨论了给定悬挂点数的单圈图中的极小图，Petrovic[5]等讨论了双圈图中的极小图。近期也有很多关于支配数和谱半径之间关系的研究，如Clemens[6]给出了Laplace矩阵的谱半径与支配数之间的联系，Stevanovic[7]等刻画了在给定支配数的图类中邻接矩阵谱半径取得最大的图的结构，Feng[8]等确定了当支配数分别为2, 3, 4时谱半径取得最小的树的结构。受这些文献的启发，本文研究最小特征值和支配数的关系, 刻画了支配数为1的图类中极小图的结构。

设x=(x1,x2,…,xn)∈Rn, 则x可视为定义在n阶图G的顶点集V(G)上的一个函数, 对应关系为x(vi)=xi(i=1,2,…,n)。于是, 二次型xTA(G)(x)可表示为

(1)

若x是图G的属于特征值λ的特征向量，则

A(G)x=λx，即

(2)

其中,NG(u)为u在G中的邻域，(2)称为G的(λ,x)特征方程。

另外, 对任一单位向量x∈Rn, 都有

λ1(G)≤xTA(G)x

(3)

当且仅当x是G的最小向量时等式成立。

如果G是阶数大于1的连通图, 则A(G)为非负不可约矩阵, 由Perron-Frobenius定理知, 谱半径所对应的特征向量(称为Perron向量)的分量全为正数或全为负数. 由于实对称矩阵的不同特征值所对应的特征向量正交，因此G的最小向量必含正负分量。

设Dn是支配数为1的n≥3阶图构成的集合,G∈Dn, {v0}为G的一个最小支配集, 则V-{v0}中任何一点都与v0有边相连, 因此G含有一个星生成子图, 因而是连通的。

下面介绍Dn中的一个特殊图类G(p,q), 它是由完全二部图Kp,q添加一个点并连接该点到Kp,q的所有点而获得, 其中p≥q≥1; 如图1所示, 完全二部图Kp,q的两个部为V+与V-, 其中|V+|=p,|V-|=q。

图1图G(p,q), p≥q≥1, “∨”表示连接V+的每个点到V-的每个点

引理1对于给定的p,q,p≥q≥1,p+q≥3，图G(p,q)的最小向量x具有如下结构：V+中的点具有相同的值, 记为β; V-中的点也具有相同的值, 记为γ。若记x(v0)=∶α, 则有如下结论：

(1) 当p=q=∶k, 则α=0,β=-γ≠0,此时,λ1(G(p,q))=-k。

(2) 当p>q, 若设α<0,则β>0,γ<0，此时-p<λ1(G(p,q))<-q。

证明由于G(p,q)的最小特征值λ1≠0，且对∀u∈V+， 根据(λ,x)-特征方程得

所以V+中每一个点的值都相等, 记为β; 类似地, V-中的每个点的值也相等, 记为γ。记x(v0)=∶α。由 (2) 可得：

λ1α=pβ+qγ,λ1β=α+qγ,λ1γ=α+pβ

(4)

由(4) ,

(λ1+p)β=(λ1+q)γ=(λ1+1)α

(5)

由于G(p,q)含有二部子图Kp,q, 故

(6)

若p=q=∶k≥2,则λ1(G(p,q))≤-k。若λ1(G(p,q))<-k,由 (5) ,α,β,γ同号, 这是不可能的, 因为最小向量必同时含正负分量, 故λ1(G(p,q))=-k。再由 (5) 可得α=0, 从而β=-γ。

若p>q, 由 (6),λ1(G(p,q))<-q,由(5)可知α,γ同号, 不妨设为负, 则β必为正,由此可以发现, λ1+p>0, 从而λ1>-p。

证明根据 (4) , 可知λ1是如下方程的最小根:

f(p,q;λ)=∶λ3-(p+q+pq)λ-2pq=0

(7)

简单计算可得:

f(p,q;λ)-f(p-1,q+1;λ)=(p-q-1)(λ+2)

若p≥q+2,且λ<-2, 则

f(p,q;λ)-f(p-1,q+1;λ)<0

(8)

λ1(G(p,q))>λ1(G(p-1,q+1))

(9)

证明设G为Dn中的一个极小图, {v0}为G的一个最小支配集, 则V-{v0}中任何一点都与v0有边相连。设x为G的单位最小向量，记

V+={u∈V(G){v0}∶x(u)≥0},

V-={u∈V(G){v0}∶x(u)<0}。

并记|V+|=p,|V-|=q，不失一般性，令p≥q。

首先，若V+,V-中有一者为空集, 不妨设V-为空。则删去V+里所有可能的边, 得到一个星图K1,n-1∈Dn, 根据 (3)，

λ1(K1,n-1)≤xTA(K1,n-1)x≤xTA(G)x=λ1(G)

因为G为Dn中的极小图, 故上述等式成立, 从而x也为K1,n-1∈Dn的最小向量。由于星图的最小向量在V+里的点值都相等且为正, 故根据等式xTA(K1,n-1)x=xTA(G)x, 可知G=K1,n-1, 即为星图。

其次，若V+,V-都为非空集合, 则类似地, 删去V+和V-中所有的边, 并在V+中的每个点与V-中的每个点之间添上所有可能的边, 得到图G(p,q),且根据 (3),

λ1(G(p,q))≤xTA(G(p,q))x≤xTA(G)x=λ1(G)

由于G为Dn中的极小图，所以上述表达式中等式成立, 从而x也为G(p,q)的单位最小向量。当n≥4时, 由引理1, V+中每一个点的值均相等且不等于0。根据xTA(G(p,q))x=xTA(G)x, 可得G=G(p,q)。

综上所述, 当n≥4, 极小图为星图或某个G(p,q)。当n≥6时,根据 (6)

容易发现D3中仅有2个图, 即星图K1,2和完全图K3, 显然星图的极小特征值较小。根据定理1, 当n=4时, 极小图为星图K1,3或G(2，1), 计算可得K1,3的极小特征值较小。当n=5时, 极小图为星图K1,4或G(2，2)或G(3，1), 而这三个图的极小特征值都为-2。因此, 结合定理1, 本文获得如下主要结论：

参考文献:

[1] Bell F K, Cvetkovic D, Rowlinson P, Simic S K. Graph for which the least eigenvalues is minimal, I. [J]. Linear Algebra and its Applications, 2008(429):234-241.

[2] Bell F K, Cvetkovic D, Rowlinson P, Simic S K. Graph for which the least eigenvalues is minimal,II. [J]. Linear Algebra and its Applications, 2008(429):2168-2179.

[3] Fan Yi-Zheng, Wang Yi, Gao Yu-Bin. Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread[J]. Linear Algebra and its Applications, 2008(429): 577-588.

[4] Liu Ruifang, Zhai Mingqing, Shu Jinlong. The least eigenvalue of unicyclic graphs with n vertices and k pendant vertices[J]. Linear Algebra and its Applications, 2009(431):657-665.

[5] Petrovic M, Borovicanin B, Aleksic T. Bicyclic graphs for which the least eigenvalue is minimum[J]. Linear Algebra and its Applications, 2009(430):1328-1335.

[6] Clemens Brand.Eigenvalues and domination in graphs[J]. Mathematica Slovaca,1996(46)：33-39.

[7] Stevanovic D, Aouchiche M, Hansen P. On the spectral radius of graphs with a given domination number[J]. Linear Algebra and Its Applications , 2008,428 (8-9) : 1854-1864.

[8] Feng Li-hua, Yu Gui-hai, Li Qiao. Minimizing the Laplacian eigenvalues for trees with given domination number[J]. Linear Algebra and Its Applications, 2006(419)：648-655.

The Least Eigenvalue of a Graph with Domination Number One

ZHA Shu-ping，Wu Qiong

(School of Mathematics and Computation Sciences, Anqing Normal University, Anqing 246133, China)

Abstract:In this paper, we characterize the graph whose least eigenvalue is minimum among all graphs with fixed order and domination number 1.

Key words:graph, adjacency matrix, least eigenvalue, domination number

文章编号：1007-4260(2015)02-0004-03

中图分类号：O157

文献标识码：A

作者简介：查淑萍，女，安徽怀宁人，安庆师范学院数学与计算科学学院硕士研究生。

收稿日期：2014-12-16