圖譜確定問題綜述

王 衛(wèi)

(西安交通大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 陜西西安 710049)

圖譜蘊含著圖的大量組合結(jié)構(gòu)信息，一直以來是圖論研究中強有力的工具. “哪些圖是譜確定的？”是圖譜理論中一個長期未解決的基本問題，該問題最早可追溯到兩位化學(xué)家Günthard和Primas于1956年發(fā)表的文章[1]，他們將圖譜理論與化學(xué)中Hückel的分子軌道理論聯(lián)系在了一起.譜確定問題的另一個主要研究動機源于圖論中的一個最基本的問題——圖同構(gòu)問題，即給定兩個圖，判定它們是否同構(gòu).由于在計算復(fù)雜性理論中占有獨特地位,該問題一直以來備受人們關(guān)注.最近Babai[2]取得了突破性進展，給出了圖同構(gòu)問題的擬多項式時間算法，為三十多年來最好的結(jié)果，但該問題到底屬于 P 還是NP-完全問題仍懸而未決.

圖譜確定問題還與其他領(lǐng)域的一些問題有緊密聯(lián)系.1966年，Kac[3]提出了一個著名問題：“我們能聽鼓辨出其形狀嗎？”Fisher[4]考慮了這個問題,他將鼓的形狀用一個圖來模擬,而鼓的聲音則由圖譜刻劃.這樣Kac的問題本質(zhì)上就是圖譜確定問題.這一問題可進一步推廣至黎曼幾何中,見文獻[5-8].

van Dam等[9-10]分別于2003年和2009年發(fā)表了關(guān)于上述問題的綜述文章.現(xiàn)在十余年過去了，這一領(lǐng)域也取得了一些新的進展，本文主要對近十年來這一領(lǐng)域的一些新成果加以整理回顧，并列出一些仍亟待解決的問題，希望引發(fā)進一步的研究.

現(xiàn)在引入一些概念和符號.給定一個簡單圖G,令M=M(G)為與圖G關(guān)聯(lián)的矩陣，譬如M可以是圖的鄰接矩陣A、拉普拉斯矩陣L、無符號拉普拉斯矩陣Q,距離矩陣D等.矩陣M的特征值全體(包括重述)稱為圖的M-譜，記為SpecM(G).本文主要考慮圖的鄰接譜、(無符號)拉普拉斯譜、距離譜，以及廣義譜.兩個圖G,H稱為M-同譜，如果它們關(guān)于M-矩陣的譜相同，即SpecM(G)=SpecM(H).一個圖G稱為由其M-譜確定(determined by itsM-spectrum,簡稱DMS)， 如果對任意圖H, 有SpecM(G)=SpecM(H)蘊含H同構(gòu)于G.若一個圖G是M-譜確定的，則稱之為DMS-圖.

本文簡要闡述了關(guān)于圖的鄰接譜確定的一些結(jié)果，給出了(無符號)拉普拉斯譜確定性，詳細介紹了圖譜距離譜確定性，討論了圖的廣義譜確定性的一些結(jié)果.

1 圖的鄰接譜確定性

本節(jié)考慮圖關(guān)于鄰接矩陣A的譜確定性.現(xiàn)有的DAS-圖大都具有以下特點：該圖或其補圖的譜半徑很小.通過譜半徑的估計確定同譜圖的度序列，然后將可能的同譜不同構(gòu)的圖類加以排除.早期人們已經(jīng)得到了一類特殊樹，譬如Zn,T-型樹T(a,b,c)，以及一般的星型樹的譜刻畫.近年來又有更多的特殊圖類被證明是DAS的.

一個風箏圖(Kite graph)是由一個p個頂點的完全圖Kp的一個頂點連接一個q個頂點的懸掛路得到的圖，Topcu等[11]證明了下述定理:

定理1.1[11]所有風箏圖可由其鄰接譜確定.

一個菠蘿圖，記為Kpq(p≥3,q≥1)，是由一個p個頂點的完全圖通過在一個頂點加q條懸掛邊得到的圖.Topcu等[12-13]證明了以下結(jié)果：

定理1.2 如果限定在連通圖類中，Kpq(p≥3,q≥1)可由其鄰接譜確定.反之可以確定所有的p，q使得存在一個不連通圖與KpqA-同譜且不同構(gòu).

一個啞鈴圖，記為Da,b,c，是由兩個不交圈Ca和Cb通過一條c+3個頂點的路Pc+3分別連接兩個端點得到的圖.Wang等[14]得到了下述結(jié)果：

定理1.3 不含4-圈C4的啞鈴圖Da,b,c可由其鄰接譜確定.

一個圖稱為友誼圖(Friendship graph)，記為Fk，是k個邊不相交的三角形將其中每個三角形恰選一個頂點粘合在一起得到的圖(風車圖).Wang等[15]猜測友誼圖是DAS的.Das[16]聲稱給出了一個證明.Abdollahi等[17]指出證明中的一個錯誤，并證明了一些特殊情形.Cioab?等[18]通過分析僅有兩個特征值不等于±1的圖，得到了友誼圖譜確定性的下述完整結(jié)果：

定理1.4 友誼圖Fk當k≠16時是DAS的.

Ramezani等[19]證明了下述結(jié)果：

定理1.5 一個奇圈與K2的笛卡爾積C2t+1×K2是DAS的.

Camara等[20]研究了何時一個完全圖刪去一些邊得到的圖是DAS的.他們提出以下猜想：

猜想1.1 令Pl為一個完全圖Kn的子圖，Kn刪去Pl后得到的圖記為Kn〗Pl，則Kn〗Pl對于所有1≤l≤n是DAS的.

上述猜想當l=n時成立，這是Doob等[21]中的主要結(jié)果.對該猜想的一些特殊情形，有以下定理：

定理1.6 上述猜想當l≤5時成立.

定理1.7[22]上述猜想當l=7,8,9時成立.

需要指出的是，近年來Koolen等[23-24]發(fā)展了Hofmman等關(guān)于線圖刻畫的深刻理論，得到了最小特征值大于-3的圖的一些刻畫.基于此，他們能夠證明，譬如兩個完全圖Kt的笛卡爾乘積構(gòu)成的t×t-格子圖的2-團擴張(即將每個頂點換成K2，新的頂點相鄰當且僅當原來的頂點相鄰)是DAS的，即：

定理1.8[25]當t足夠大時，(t+1) × (t+1)-格子圖的2-團擴張圖是DAS的.

2 圖的(無符號)拉普拉斯譜確定性

給定一個圖G，其鄰接矩陣為A，度對角矩陣為D，則拉普拉斯矩陣定義為L=D-A；無符號拉普拉斯矩陣定義為Q=D+A.圖的拉普拉斯譜可確定圖的連通分支數(shù)目及生成數(shù)數(shù)目；無符號拉普拉斯譜可確定一個圖二部圖的分支數(shù)目.這些在研究圖譜確定問題中都有重要應(yīng)用.

一個有k個花瓣的k-玫瑰圖，記為G=R(m1,m2,…,mk)，是由恰好有一個公共頂點的m個圈Cm1,Cm2,…,Cmk構(gòu)成的圖，若k=2， 則該圖稱為一個∞-圖.Wang等[26]，Liu等[27]證明了以下結(jié)果：

定理2.1一個3-玫瑰圖可由無符號拉普拉斯譜確定；一個3-玫瑰圖則可由拉普拉斯譜確定.

定理2.2[28]一個沒有三角形的∞-圖是DLS的;∞-圖是DLS的.

關(guān)于玫瑰圖，He等[29]證明了下述一般性結(jié)果：

定理2.3 除了R(3,4)和R(3,5)外，所有k-玫瑰圖是DLS.

一個蝴蝶圖是一個玫瑰圖在其中心再添加一些懸掛的路得到的圖.Wen等[30]猜測：所有蝴蝶圖是DLS的，同時也是DQS的.Liu等[31]證實了該猜想是正確的：

定理2.4 所有蝴蝶圖既是DLS的，同時也是DQS的.

一個星型樹，記為T=T(l1,l2,…,lk)，是一個恰有一個頂點度大于2的樹，令v為其最大度，則T(l1,l2,…,lk)-v=Pl1∪Pl2∪…Plk.早期Lepovic 和Gutman證明了沒有兩個星型樹A-同譜；Wang和Xu得到了當k=3時所有DAS的T-型樹，并證明了所有T-型樹是DLS的；Omidi等證明了所有星型樹是DLS的；Omidi[32]得到了所有DQS的T-型樹；Omidi等[33]證明了最大度為4的星型樹是DQS的，Bu等[34]證明了一個最大度大于4的星型樹是DQS的，從而有以下結(jié)果：

定理2.5 最大度大于3的星型樹是DQS.

Zhou等[35]考慮了一類乘積圖的DLS性.令G,H是兩個頂點不交的圖，G,H的乘積，記為G×H，是一個由G∪H通過連接G的每個頂點與H的每個頂點得到的圖.譬如Cn×K1是一個輪圖.

定理2.6[35]令G是一個不連通的DLS圖，則G×Km是DLS的.

定理2.7[35]令G是一個至少有5個頂點的DLS樹，或是一個至少有6個頂點的單圈DLS圖，則G×Km是DLS的.

定理2.8 完全分裂圖CS(n,α)(1≤α≤n-1)是DQS的；完全分裂圖CS(n,α)(1≤α≤n-1,α≠3) 是DLS的.

關(guān)于拉普拉斯譜有以下問題：

問題：一個樹的度序列可否由拉普拉斯譜確定？

3 圖的距離譜確定性

給定一個連通圖G，其距離矩陣D(G)=(dij)n×n，其中dij為頂點i與j之間的距離.令ti=∑d(vi,vj)為頂點vi到其余頂點的距離之和.令T(G)=diag(t1,t2,…,tn)，則圖G的距離拉普拉斯矩陣定義為L(G)=T(G)-D(G)，距離無符號拉普拉斯矩陣定義為Q(G)=T(G)+D(G).圖的距離各種譜及距離譜確定性近年來得到了廣泛關(guān)注，見文獻[37].

Lin等[38]刻畫了最小距離特征值λn(D)=-2且重數(shù)為n-k的圖——這樣的圖為完全k-部圖(2≤k≤n-1).他們證明了完全二部圖及完全split圖是距離譜確定的，并提出了以下猜想：

猜想3.1 令G=Kn1,n2,…,nk為一個完全k-部圖,則G可由其距離譜確定.

Jin等[39]證明了上述猜想成立:

定理3.1 完全k-部圖可由其距離譜確定.

一個雙星樹，記為S(a,b)，是由兩個相交的星型樹K1,a和K1,b通過添加一條邊連接其中心得到的圖.Xue等[40]證明了下述結(jié)果：

定理3.2 一個雙星樹S(a,b)是距離譜確定的.

Xue等[41]，Lin等[42]考慮了圈與道路以及其補圖的距離譜確定性.

定理3.3 一個圈Cn和道路Pn的補圖分別可由距離譜，距離(無符號)-拉普拉斯譜確定.

一個d-超立方體可定義如下：其頂點集為所有長度為d的(0，1)——向量，兩個向量相鄰當且僅當它們恰有一個分量不相同.Koolen等[43]證明了下述定理：

定理3.4d-超立方體可由其距離譜確定.

Aouchiche等[46]利用計算機進行數(shù)值研究了10個頂點以內(nèi)圖的關(guān)于距離譜，(無符號)拉普拉斯距離譜同譜的所有圖，確定了其中的譜確定圖.

關(guān)于圖的距離譜有以下問題[43]：

問題1： 圖的距離譜是否可以決定該圖是否是二部圖？

問題2：一個距離正則圖和一個非距離正則圖是否能夠有相同距離譜？

問題3：Hamming圖H(d,q)當q≠4時是否是距離譜確定的？

4 圖的廣義譜確定性

圖的廣義譜確定最早是由Wang等[47]研究的,他們給出了一般隨機生成圖的DGAS性判定方法.令W=[e,Ae,…,An-1e]為圖G的路矩陣(Walk-matrix),一個圖G稱為是可控圖(Controllable graph)如果W非奇異.Godsil[48]猜想幾乎所有圖是可控制圖，最近O’Rourke等[49]證明了該猜想成立.

Wang等[47]提出的方法主要基于以下觀察：

定理4.1 令G是一個可控圖,則一個圖H與G廣義A-同譜當且僅當存在唯一的一個有理正交矩陣Q,使得QTA(G)Q=A(H),Qe=e，其中e為分量權(quán)全為1的向量.

定理4.2[47]一個可控圖G是DGAS的當且僅當Γ(G)僅包含置換矩陣.

由上述定理，若能證明Γ(G)中所有有理正交矩陣都是置換矩陣，則G是DGAS的.為證明這一點，定義一個有理正交矩陣的級為最小正整數(shù)l=l(Q),使得lQ為一個整數(shù)矩陣.顯然一個滿足Qe=e的有理正交矩陣Q是置換矩陣當且僅當它的級為1.進一步，若能證明?Q∈Γ(G)，對任意素數(shù)p有p不能整除l(Q)，則一定有l(wèi)=1，從而Q為置換矩陣.基于上述思想，Wang[50-51]得到了以下結(jié)果：

定理4.3 如果det(W)/2[n/2](該數(shù)總是整數(shù))是無平方因子的奇數(shù)，則G是DGAS的.

Wang[50]對滿足上述定理的隨機圖進行了大量數(shù)值試驗，結(jié)果表明有大量的DGAS圖存在(下界約為20%).

表1 DGAS圖的比例

上述定理在一定意義下是最優(yōu)的，即若det(W)/2[n/2]有平方因子，則一定條件下圖G是非DGAS的.

定理4.4[52]令G為一個可控圖，p為一個奇素數(shù).假定以下條件成立：

(i)p2|det(W)；

(ii)W在有限域的秩rankp(W)=n-1；

(iii)方程組WTx≡0(modp)有下述形式的解：(1,1…,1,-1,-1,…,-1,0,0,…,0)T，其中1與-1的個數(shù)均為p.

則存在一個圖H與G廣義同譜且不同構(gòu).

類似的結(jié)果也可以對廣義Q-譜(無符號拉普拉斯譜)成立.令WQ=[e,Qe,…,Qn-1e]為Q-路矩陣.

定理4.5[53]若det(WQ)/2[3n-2/2](該數(shù)總是整數(shù))是無平方因子的奇數(shù)，則G是DGQS的.

關(guān)于DGAS圖的構(gòu)造，Mao等[54]及Liu等[55]給出了下述結(jié)果.令G°K2為圖G與K2的根積(即在G的每個頂點添加一個懸掛邊得到的圖),則有

定理4.6[54]若G的特征多項式的常數(shù)項為±1，且det(W(G))=±2n/2(n為偶數(shù))，則G°K2是DGAS的.

上述定理給出了顯式構(gòu)造無窮DGAS圖序列的一個方法：從一個滿足上述定理條件的小圖G出發(fā)，不斷構(gòu)造G°K2,(G°K2)°K2,…，則該序列中每個圖都是DGAS的.

Liu等[55]給出了下述構(gòu)造方法：從一個初始圖G0出發(fā)，不斷交替添加孤立頂點及取聯(lián)(Join)，則G0滿足一定條件下可以得到一個DGAS圖的無窮序列.

關(guān)于圖的廣義譜確定性，可以提出以下問題：

問題1：如何判定非可控圖的廣義譜確定性？

問題2： 圖的廣義譜確定的有關(guān)結(jié)果是否可以推廣至其他譜(譬如鄰接譜、拉普拉絲譜等)？

問題3：能否證明廣義譜確定圖具有正的密度？

5 結(jié)束語

本文對圖譜確定問題近年來的進展進行了簡單的總結(jié)回顧，由于篇幅所限，很多相關(guān)話題未能涉及，所列結(jié)果也遠非完全.目前該領(lǐng)域雖取得了很多進展，但仍有大量問題需要進一步研究，特別是Haemaer在2003年提出以下猜想——猜想(Haemers)：幾乎所有圖(關(guān)于鄰接譜、拉普拉斯譜等)是譜確定的.

目前關(guān)于該猜想仍所知甚少，希望未來能發(fā)展出進一步的工具，對包括上述猜想在內(nèi)的很多問題取得一些實質(zhì)性的進展.