支配數為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