黃龍，高珊，趙芹，陳寒冰

(1．湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北 武漢 430062；2.湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院，湖北 武漢 430062；3.應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室(湖北大學(xué))，湖北 武漢 430062)

0 引言

圖的特征值與最大割問題(MCP)之間的關(guān)系可以追溯到1847年的矩陣-樹定理.1990年, Mohar-Poljak[5]給出了圖的最大割與圖的拉普拉斯矩陣L的最大特征值有關(guān)的上界,并稱上界可達(dá)時(shí)對(duì)應(yīng)的圖為L(zhǎng)-精確圖(L-exact graph).Alencar-Lima[4]分別給出了圖的最大割與鄰接矩陣A和無符號(hào)拉普拉斯矩陣Q的最小特征值有關(guān)的上界,并類似地定義了A-精確圖和Q-精確圖.Alencar-Lima[4]給出了圖的鄰接矩陣、拉普拉斯矩陣和無符號(hào)拉普拉斯矩陣的特征值對(duì)應(yīng)的特征向量的分量的元素僅有±1組成的充分必要條件, 從而解決了關(guān)于圖的鄰接矩陣,拉普拉斯矩陣和無符號(hào)拉普拉斯矩陣的Wilf問題.

2016年,Nikiforov[6]定義了圖的Aα矩陣，其融合了圖的鄰接矩陣和無符號(hào)拉普拉斯矩陣.本文中，我們首先定義Aα-精確圖，接著給出Aα矩陣的特征值對(duì)應(yīng)的特征向量的分量的元素僅有±1組成的圖的結(jié)構(gòu)的刻畫,從而解決了關(guān)于圖的Aα矩陣的Wilf問題. 最后給出判斷一個(gè)圖是Aα-精確圖的一個(gè)充分條件.

1 定義和記號(hào)

對(duì)于X?V(G)和E′?E(G),G[X]表示G的由X導(dǎo)出的子圖，G[E′]表示G的由邊集E′導(dǎo)出的子圖[7].

令X和Y為圖G的兩個(gè)頂點(diǎn)集(X∩Y不一定為空集).E[X,Y]表示G中端點(diǎn)分別在X和Y中的邊集合,當(dāng)X=Y時(shí),E[X,Y]記為E[X].

圖G關(guān)于X的邊割(cut)cutG(X)和內(nèi)聚(cohesion)cohG(X)分別定義為：

注意到cohG(X)+cutG(X)=W(G).

令en為全1向量,G[X](X?V(G))的鄰接矩陣表示為AX,由邊集E(X,Y)導(dǎo)出的子圖表示為G[X,Y],X?V(G)中的頂點(diǎn)在G中的度對(duì)角矩陣表示為DX.

2 Aα-exact圖

我們有

(1)

引理2.1[4]令U為V的子集,U使得cutG(U)最大當(dāng)且僅當(dāng)U使得cohG(U)最小.

文獻(xiàn)[6]中給出了圖的最大割關(guān)于Aα矩陣的最小特征值的一個(gè)上界.為了刻畫圖的最大割上界可達(dá)時(shí)的條件,我們給出引理2.2的證明.

引理2.2[6]令G=(V,E,w)為一個(gè)n階的賦權(quán)圖,W表示為G中全部邊的權(quán)重之和.有

(2)

根據(jù)Mohar-Poljak[5]對(duì)精確(exact)圖的定義,我們類似地定義Aα-精確圖.

3 Aα矩陣的Wilf問題的證明

本節(jié)我們考慮關(guān)于圖Aα矩陣的Wilf問題,即何種圖的Aα矩陣的某個(gè)特征值對(duì)應(yīng)的特征向量的分量的元素僅由±1組成.我們給出了賦權(quán)圖G存在其Aα矩陣的特征值對(duì)應(yīng)的特征向量為劃分向量ps的充分必要條件,其中S?V(G),從而解決了關(guān)于圖的Aα矩陣的Wilf問題.最后給出了圖是Aα-精確圖的一個(gè)充分條件.

定理3.1令G=(V,E,w)為n階賦權(quán)圖,S?V,λα是Aα的特征值,則pS是λα的特征向量當(dāng)且僅當(dāng)

根據(jù)定理3.1, 我們得到了圖是Aα-精確圖的一個(gè)充分條件,即推論3.1.

推論3.1令G=(V,E,w)為n階賦權(quán)圖,S是V的子集,ps為S的劃分向量.如果圖G滿足下列3個(gè)條件：

1)cutG(S)=mcut(G);

則G是Aα-精確圖.