查淑萍，吳　瓊

(安慶師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

?

支配數(shù)為1的圖的最小特征值

查淑萍，吳瓊

(安慶師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

摘要：本文中主要刻畫了給定階數(shù)且支配數(shù)為1的圖類中最小特征值達(dá)到極小的圖的結(jié)構(gòu)。

關(guān)鍵詞：圖; 鄰接矩陣; 最小特征值; 支配數(shù)

圖G的一個(gè)支配集是圖G的頂點(diǎn)集V(G)的一個(gè)子集X，使得對(duì)V(G)-X中的任一頂點(diǎn)至少與X中的一個(gè)頂點(diǎn)相鄰,其中頂點(diǎn)數(shù)最少的支配集稱為圖G的最小支配集，而最小支配集中所含的頂點(diǎn)數(shù)稱為圖G的支配數(shù)。

關(guān)于圖的譜半徑，已經(jīng)有了很多的研究結(jié)果，而近年來(lái)，有很多研究者也在關(guān)注圖的最小特征值的研究，尤其是刻畫某圖類中的極小圖，如Bell[1,2]等刻畫了給定邊數(shù)的圖中的極小圖,Fan等[3]刻畫了給定圍長(zhǎng)的單圈圖中的極小圖，Liu[4]等討論了給定懸掛點(diǎn)數(shù)的單圈圖中的極小圖，Petrovic[5]等討論了雙圈圖中的極小圖。近期也有很多關(guān)于支配數(shù)和譜半徑之間關(guān)系的研究，如Clemens[6]給出了Laplace矩陣的譜半徑與支配數(shù)之間的聯(lián)系，Stevanovic[7]等刻畫了在給定支配數(shù)的圖類中鄰接矩陣譜半徑取得最大的圖的結(jié)構(gòu)，F(xiàn)eng[8]等確定了當(dāng)支配數(shù)分別為2, 3, 4時(shí)譜半徑取得最小的樹的結(jié)構(gòu)。受這些文獻(xiàn)的啟發(fā)，本文研究最小特征值和支配數(shù)的關(guān)系, 刻畫了支配數(shù)為1的圖類中極小圖的結(jié)構(gòu)。

設(shè)x=(x1,x2,…,xn)∈Rn, 則x可視為定義在n階圖G的頂點(diǎn)集V(G)上的一個(gè)函數(shù), 對(duì)應(yīng)關(guān)系為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)特征方程。

另外, 對(duì)任一單位向量x∈Rn, 都有

λ1(G)≤xTA(G)x

(3)

當(dāng)且僅當(dāng)x是G的最小向量時(shí)等式成立。

如果G是階數(shù)大于1的連通圖, 則A(G)為非負(fù)不可約矩陣, 由Perron-Frobenius定理知, 譜半徑所對(duì)應(yīng)的特征向量(稱為Perron向量)的分量全為正數(shù)或全為負(fù)數(shù). 由于實(shí)對(duì)稱矩陣的不同特征值所對(duì)應(yīng)的特征向量正交，因此G的最小向量必含正負(fù)分量。

設(shè)Dn是支配數(shù)為1的n≥3階圖構(gòu)成的集合,G∈Dn, {v0}為G的一個(gè)最小支配集, 則V-{v0}中任何一點(diǎn)都與v0有邊相連, 因此G含有一個(gè)星生成子圖, 因而是連通的。

下面介紹Dn中的一個(gè)特殊圖類G(p,q), 它是由完全二部圖Kp,q添加一個(gè)點(diǎn)并連接該點(diǎn)到Kp,q的所有點(diǎn)而獲得, 其中p≥q≥1; 如圖1所示, 完全二部圖Kp,q的兩個(gè)部為V+與V-, 其中|V+|=p,|V-|=q。

圖1圖G(p,q), p≥q≥1, “∨”表示連接V+的每個(gè)點(diǎn)到V-的每個(gè)點(diǎn)

引理1對(duì)于給定的p,q,p≥q≥1,p+q≥3，圖G(p,q)的最小向量x具有如下結(jié)構(gòu)：V+中的點(diǎn)具有相同的值, 記為β; V-中的點(diǎn)也具有相同的值, 記為γ。若記x(v0)=∶α, 則有如下結(jié)論：

(1) 當(dāng)p=q=∶k, 則α=0,β=-γ≠0,此時(shí),λ1(G(p,q))=-k。

(2) 當(dāng)p>q, 若設(shè)α<0,則β>0,γ<0，此時(shí)-p<λ1(G(p,q))<-q。

證明由于G(p,q)的最小特征值λ1≠0，且對(duì)?u∈V+， 根據(jù)(λ,x)-特征方程得

所以V+中每一個(gè)點(diǎn)的值都相等, 記為β; 類似地, V-中的每個(gè)點(diǎn)的值也相等, 記為γ。記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) ,α,β,γ同號(hào), 這是不可能的, 因?yàn)樽钚∠蛄勘赝瑫r(shí)含正負(fù)分量, 故λ1(G(p,q))=-k。再由 (5) 可得α=0, 從而β=-γ。

若p>q, 由 (6),λ1(G(p,q))<-q,由(5)可知α,γ同號(hào), 不妨設(shè)為負(fù), 則β必為正,由此可以發(fā)現(xiàn), λ1+p>0, 從而λ1>-p。

證明根據(jù) (4) , 可知λ1是如下方程的最小根:

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

(7)

簡(jiǎn)單計(jì)算可得:

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)

證明設(shè)G為Dn中的一個(gè)極小圖, {v0}為G的一個(gè)最小支配集, 則V-{v0}中任何一點(diǎn)都與v0有邊相連。設(shè)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-中有一者為空集, 不妨設(shè)V-為空。則刪去V+里所有可能的邊, 得到一個(gè)星圖K1,n-1∈Dn, 根據(jù) (3)，

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

因?yàn)镚為Dn中的極小圖, 故上述等式成立, 從而x也為K1,n-1∈Dn的最小向量。由于星圖的最小向量在V+里的點(diǎn)值都相等且為正, 故根據(jù)等式xTA(K1,n-1)x=xTA(G)x, 可知G=K1,n-1, 即為星圖。

其次，若V+,V-都為非空集合, 則類似地, 刪去V+和V-中所有的邊, 并在V+中的每個(gè)點(diǎn)與V-中的每個(gè)點(diǎn)之間添上所有可能的邊, 得到圖G(p,q),且根據(jù) (3),

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

由于G為Dn中的極小圖，所以上述表達(dá)式中等式成立, 從而x也為G(p,q)的單位最小向量。當(dāng)n≥4時(shí), 由引理1, V+中每一個(gè)點(diǎn)的值均相等且不等于0。根據(jù)xTA(G(p,q))x=xTA(G)x, 可得G=G(p,q)。

綜上所述, 當(dāng)n≥4, 極小圖為星圖或某個(gè)G(p,q)。當(dāng)n≥6時(shí),根據(jù) (6)

容易發(fā)現(xiàn)D3中僅有2個(gè)圖, 即星圖K1,2和完全圖K3, 顯然星圖的極小特征值較小。根據(jù)定理1, 當(dāng)n=4時(shí), 極小圖為星圖K1,3或G(2，1), 計(jì)算可得K1,3的極小特征值較小。當(dāng)n=5時(shí), 極小圖為星圖K1,4或G(2，2)或G(3，1), 而這三個(gè)圖的極小特征值都為-2。因此, 結(jié)合定理1, 本文獲得如下主要結(jié)論：

參考文獻(xiàn):

[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

文章編號(hào)：1007-4260(2015)02-0004-03

中圖分類號(hào)：O157

文獻(xiàn)標(biāo)識(shí)碼：A

作者簡(jiǎn)介：查淑萍，女，安徽懷寧人，安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院碩士研究生。

收稿日期：2014-12-16