鄧 波,李學良

(1.南開大學 組合數(shù)學中心，天津 300071;2.青海師范大學 數(shù)學與統(tǒng)計學院，青海 西寧 810001)

圖G的能量ε(G)定義為其鄰接矩陣特征根的絕對值之和.設G是一個具有n個頂點的圖，如果G的能量值等于n個頂點的完全圖的能量值2(n-1), 則稱圖G為邊界能量圖.介紹了近年來關于邊界能量圖研究方面的主要結果.

圖的特征根；圖能量; 邊界能量圖；拉普拉斯能量

關于圖能量及其應用的相關內容,可以參考文[2-5].

關于圖能量，一個很自然的問題是: 哪類圖具有最大的圖能量? 起初，人們通常會認為當圖越稠密，則對應圖的圖能量越大，因此認為完全圖Kn具有最大的圖能量，其能量值為ε(Kn)=2(n-1).實際上，存在大量的圖滿足其圖能量是大于這個值，這類圖被稱為是超能量的.超能量圖的概念提出后，陸續(xù)出現(xiàn)許多尋找和刻畫超能量圖的結果[6-8]，不過這個研究方向很快被發(fā)現(xiàn)是平凡的，原因是Nikiforov通過使用概率方法證明了幾乎所有的圖都是超能量的.類似地，如果具有n個頂點的圖G的圖能量小于n(或者n-1),則圖G是次能量的(或者是強次能量的)，相關的研究結果見文[9-11].

次能量圖的概念源于化學實驗，人們在化學研究中很早就發(fā)現(xiàn)絕大多數(shù)分子圖的能量是大于其頂點數(shù)的.1973年理論化學家England和Ruedenberg發(fā)表在J.Am.Chem.Soc.上的一篇文章曾提到這樣一個問題[12]: 為什么化合物的能量總大于其化學圖的階數(shù)? 圍繞這個問題,Gutman等[9]進行了相關的研究，給出具有n個頂點和最大度為Δ的樹是次能量的充分條件，并且分別證明當Δ=3,4和Δ≥5時，次能量樹的存在性.

定理1[9](a) 如果Δ=3, 則僅當n=4和n=7時，存在次能量樹.

(b) 如果Δ=4, 則當n≥5和滿足n≡k(mod 4),k=0,1,3時，存在次能量樹.

(c) 如果Δ≥5, 則當n≥Δ+1時，存在次能量樹.

然而當最大度Δ至多為3時，除了如下幾個特殊樹外，都不存在次能量樹.

定理2[9]除了樹S1,S2,S3和W(見圖1)，不存在最大度至多3的次能量樹.

圖1 樹S1,S2,S3和W

Li等[10]證明了完全二部圖K2,3是唯一含圈的滿足Δ≤3的次能量連通圖，同時找出了所有的滿足Δ≤3的次能量連通圖.

定理3[10]完全二部圖K2,3是唯一含圈的滿足Δ≤3的次能量連通圖.

定理4[10]圖S1,S2,S3,W和K2,3是僅有的5個滿足Δ≤3的次能量連通圖.

定理5[13-14]在n個頂點和Δ≤3的連通圖中，恰好存在4個連通圖G∈{K2,K2,2,Q,K3,3}(見圖2)，滿足ε(G)=n.

圖2 圖K2,K2,2,Q和K3,3

化學圖一般是指最大度不超過3的圖.由上可見，只有少數(shù)幾個圖同時滿足Δ≤3和ε(G)=n, 所以，這從理論上證明了化學家們在文[12]中觀察的結果是正確的.然而當ε(G)=2(n-1)時，Gong等[15]發(fā)現(xiàn)存在大量的圖滿足這個條件.2015年，Gong等[15]提出邊界能量圖的概念: 如果G是一個具有n個頂點的圖，滿足G的圖能量值與n個頂點的完全圖的圖能量值相等且為ε(G)=2(n-1),則稱圖G為邊界能量的.類似地，Tura[16]把邊界能量的概念推廣到拉普拉斯能量.設μ1≥μ2≥…≥μn-1≥μn是圖G的拉普拉斯特征根，圖G的拉普拉斯能量定義如下

論文主要介紹近年來關于邊界能量圖的主要結果.內容安排如下: 第一部分介紹邊界能量圖的搜索與構造方面的結果; 第二部分介紹邊界能量圖的邊數(shù)的下界; 第三部分介紹在度條件下邊界能量圖的結構性質方面的結果；第四部分介紹拉普拉斯邊界能量圖方面的結果.

1 邊界能量圖的搜索與構造

為了研究邊界能量圖的存在性，Gong等[15]通過計算機搜索的方式，找出頂點數(shù)不超過9的所有非完全邊界能量圖.特別地，當頂點數(shù)小于7時，不存在非完全邊界能量圖.當頂點數(shù)分別為7，8，9時，則有命題1～3.

命題1[15]最小的非完全邊界能量圖G0具有7個頂點，17條邊，而且是唯一的(見圖3).

圖3 最小的非完全邊界能量圖G0,其鄰接譜為Sp(G0)={5,1,-1,-1,-1,-1,-2}

命題2[15]頂點數(shù)為8的非完全邊界能量圖恰好存在6個(見圖4).

圖4 6個具有8個頂點的非完全邊界能量圖

命題3[15]頂點數(shù)為9的非完全邊界能量圖恰好存在17個(見圖5).

圖5 17個具有9個頂點的非完全邊界能量圖

當頂點數(shù)為10時，Li等[20]通過計算機搜索找到49個非完全邊界能量圖.當頂點數(shù)為11時，Shao等[21]以同樣的方式搜索找到158個非完全邊界能量圖.故當頂點數(shù)不超過11時，所有非完全邊界能量圖已全部找到.然而當頂點數(shù)很大時，也存在非完全邊界能量圖，而且存在大量的這樣的圖.接下來將通過如下幾種方式展示如何構造非完全邊界能量圖.

方式1 圖的張量積.兩個圖G1和G2的張量積G1?G2, 是以V(G1)×V(G2)為點集，兩個頂點(u1,u2)與(v1,v2)相鄰，當且僅當u1v1∈E(G1)和u2v2∈E(G2). 基于張量積，則有定理6.

定理6[15]設G是一個邊界能量圖，假設G是兩個整譜圖G1和G2的張量積，則|V(G1)|和|V(G2)|都是奇數(shù).

方式2 強正則圖.設G是具有n個頂點的k-正則非完全圖，如果滿足每對相鄰頂點有a個共同的鄰點，每對不相鄰的頂點有c個共同的鄰點，則稱G是一個具有參數(shù)(n,k,a,c)的強正則圖.在(n,k,a,c)-強正則圖G中，如果其鄰接譜滿足

定理7[15]設G是一個會議圖，而且滿足是整譜的和非完全邊界能量的，則G具有參數(shù)(9,4,1,2).

方式3 正則圖、補圖與圖的并運算.使用正則圖及其補圖在圖譜上的性質，Gong等[15]構造出一類邊界能量圖.

由定理7、8證明了邊界能量圖的存在性.

定理9[15]對任意的整數(shù)n≥7, 總存在頂點為n的連通非完全邊界能量圖.

由定理11，可以推出當頂點數(shù)n滿足某些整除條件，則總存在一些連通的正則的非完全邊界能量圖.

定理12[22]對任意滿足5|(n-12)的整數(shù)n(n>12)，則總存在連通的(n-5)-正則的非完全邊界能量圖.

定理13[22]對任意滿足7|(n-16)的整數(shù)n(n>16)，則總存在連通的(n-7)-正則的非完全邊界能量圖.

除了上述方式可以構造大量的連通非完全邊界能量圖外，還可以利用線圖性質和一些特殊圖類的圖譜性質.因為已發(fā)現(xiàn)正則圖與其對應的線圖在特征根上存在一定的關系，故使用它們之間的關系可以找到非完全邊界能量圖.Gong等[15]發(fā)現(xiàn)Petersen圖的線圖是連通的非完全邊界能量圖.Hou等[23]利用門檻圖的圖譜性質構造出若干類非正則非整譜的連通的非完全邊界能量圖.

2 邊界能量圖邊數(shù)的下界

觀察圖3～5可見，邊界能量圖都比較稠密，人們自然會考慮這樣的問題: 對于任意一個連通的非完全邊界能量圖，至少需要多少條邊? 接下來的結果會給出邊界能量圖的邊數(shù)漸進緊的下界.先介紹頂點的r-度概念.對于整數(shù)r≥0和頂點vi∈V(G), 頂點vi的r-度定義為從vi出發(fā)的長為r的路徑個數(shù)，記為dr(vi). 顯然，當r=1,d1(vi)就是頂點vi的度，記為di. 當r=2,3, 分別記d2(vi)和d3(vi)為ti,σi.

定理14[22]設G是邊界能量圖，則

(1)

如果G是(n-3)-正則，則(1)中的界是漸進緊的.

由定理14，可以得到推論1～3.

推論1[22]設G是邊界能量圖，則

(2)

如果G是(n-3)-正則，則(2)中的界是漸進緊的.

推論2[22]設G是邊界能量圖，則

(3)

如果G是(n-3)-正則，則(3)中的界是漸進緊的.

推論3[22]設G是邊界能量圖，則

(4)

如果G是(n-3)-正則,則(4)中的界是漸進緊的.

3 最大(最小)度條件下的邊界能量圖

在化學圖論中，經常研究最大度不超過4的圖.因為這類圖有專門的化學應用背景，在研究次能量圖和其他化學指標時經常對此類圖進行研究[9-10,14].對邊界能量圖也存在相關結果，Li等[24]對滿足最大度不超過4的邊界能量圖的結構性質進行了刻畫.

定理15[24]不存在最大度為2或3的非完全邊界能量圖.

定理16[24](1) 設G是具有n個頂點和最大度Δ=4的非完全邊界能量圖，則

(i) |E(G)|=2n或者2n-1;

(ii) |V(G)|≤21;

(iii)G是非偶圖;

(iv) 特征根為0的個數(shù)為0.

(2) 設G是具有n個頂點的4正則非完全邊界能量圖，H是G的極大的偶子圖，則|E(G)|-|E(H)|≥3.

到目前為止，在有限頂點數(shù)內，只找到3個最大度為4的邊界能量圖，并且都是4-正則圖，其中2個具有9個頂點，另外一個具有15個頂點.另一方面，從最小度角度考慮，對邊界能量圖存在以下相關結果，即定理17.

定理17[24]設圖G的頂點數(shù)為n,則

(1) 不存在最小度為n-2的邊界能量圖；

(2) 對任意整數(shù)n≥7, 總存在一個具有n個頂點，最小度為n-3的連通非完全邊界能量圖；

(3) 對任意偶數(shù)n≥8, 總存在一個具有n個頂點，最小度為n-4的連通非完全邊界能量圖.

4 拉普拉斯邊界能量圖

4.1 拉普拉斯邊界能量圖的構造與搜索

從一個孤立點開始，然后每一步或者增加一個孤立點，或者與前面的頂點都相鄰，通過這種迭代方式得到的圖，稱為門檻圖.

圖的 Ferrers-Sylvester圖

圖7 門檻圖

(5)

等號成立當且僅當圖G是門檻圖.

(6)

由(6)，則

因此，由定理18可知，無論頂點數(shù)n是偶數(shù)或是奇數(shù)總存在拉普拉斯邊界能量圖，故如下的結果比Tura的結果更具有一般性.

定理19[17]對任意整數(shù)n≥4, 總存在拉普拉斯邊界能量圖.

當圖的頂點數(shù)n在范圍4≤n≤9時，所有的非完全拉普拉斯邊界能量圖已被找到[17]，具體個數(shù)見表1.

表1 頂點數(shù)n在范圍4≤n≤9的非完全拉普拉斯邊界能量圖個數(shù)

類似于定理6，使用圖的張量積可以構造拉普拉斯邊界能量圖.

定理20[17]設G是拉普拉斯整譜圖G1和G2的張量積，其中G1和G2分別是r1-正則和r2-正則.如果G是拉普拉斯邊界能量圖，則|V(G1)|和|V(G2)|都是奇數(shù).

此外，還可以通過在完全圖中去匹配的方式構造拉普拉斯邊界能量圖.

4.2 拉普拉斯邊界能量圖的邊數(shù)和頂點數(shù)

定理22[18]如果G是具有n個頂點和m條邊的拉普拉斯邊界能量圖，則

(7)

當G是4-正則時，(7)中的界是漸進緊的.

接下來使用拉普拉斯能量的Koolen-Moulton型不等式可以得到定理23.

定理23[19]如果G是具有n個頂點和m條邊的拉普拉斯邊界能量圖，滿足最大度Δ=4, 則

(8)

當G是4-正則時，(8)中的界是漸進緊的.

類似地，由拉普拉斯能量的McClelland型不等式可以得到定理24.

定理24[19]如果G是具有n個頂點和m條邊的拉普拉斯邊界能量圖，滿足最大度Δ=4, 則

(9)

當G是4-正則時，(9)中的界是漸進緊的.

定理25[18]如果G是具有n個頂點和m條邊的拉普拉斯邊界能量圖，則

(10)

定理26[18]如果G是具有n個頂點和m條邊的拉普拉斯邊界能量圖，滿足最小度δ=1, 則

(11)

實際上，可以找到拉普拉斯邊界能量圖使得(11)中的等號成立.當n=4,6,8時，如下的3個圖滿足等號要求(見圖8).

4.3 非拉普拉斯邊界能量圖

Deng等[18]陸續(xù)證明了所有的樹、圈、完全二部圖和大部分2-連通圖都不是拉普拉斯邊界能量圖.如下這類2-連通圖不是拉普拉斯邊界能量圖，令t(G)為圖G中度為3的頂點的個數(shù)，有定理27.

定理27[18]如果G是滿足最大度Δ=3和t(G)≥7的2-連通圖，則G不是拉普拉斯邊界能量圖.

通過使用Cauchy-Schwarz不等式，定理27中的條件t(G)≥7是可以去掉的，得定理28.

定理28[19]如果G是滿足最大度Δ=3的2-連通圖，則G不是拉普拉斯邊界能量圖.

圖8 頂點數(shù)分別為4,6,8和滿足δ=1的拉普拉斯邊界能量圖

5 后續(xù)研究

觀察邊界能量圖和拉普拉斯邊界能量圖已有的結果，可以看到，這些圖的比較深入的結構特性并沒有完全被刻畫，后續(xù)研究可以考慮刻畫這些圖類的最大(最小)譜半徑、圍長、最大匹配數(shù)、最大團的點數(shù)等方面性質.

[1] GUTMAN I. Acylclic systems with extremal Hückel π-electron energy[J]. Theor Chim Acta， 1977 (45): 79-87.

[2] GUTMAN I. The energy of a graph[J]. Math-Statist Sekt Forschungsz Graz， 1978 (103): 1-22.

[3] GUTMAN I， LI X， ZHANG J. Graph energy[M]. Weinheim: Emmert-Streib， 2009: 145-174.

[4] GUTMAN I， POLANSKY O E. Mathematical concepts in organic chemistry[M]. Berlin: Springer, 1986.

[5] LI X， SHI Y， GUTMAN I. Graph Energy[M]. New York: Springer, 2012.

[6] AKBARI S， MOAZAMI F， ZARE S. Kneser graphs and their complements are hyperenergetic[J]. MATCH Commun Math Comput Chem， 2009 (61): 361-368.

[7] HOU Y， GUTMAN I. Hyperenergetic line graphs[J]. MATCH Commun Math Comput Chem， 2001 (43): 29-39.

[8] STEVANOVIC D， STANKOVIC I. Remarks on hyperenergetic circulant graphs[J]. Lin Algebra Appl， 2005 (400): 345-348.

[9] GUTMAN I， LI X， SHI Y， et al. Hypoenergetic trees[J]. MATCH Commun Math Comput Chem， 2009 (60): 415-426.

[10] LI X， MA H. All hypoenergetic graphs with maximum degree at most 3[J]. Linear Algebra Appl， 2009 (431): 2127-2133.

[11] LI X， MA H. Hypoenergetic and strongly hypoenergetick-cyclic graphs[J]. MATCH Commun Math Comput Chem， 2010 (64): 41-60.

[12] ENGLAND W， RUEDENBERG K. Why is the delocalization energy negative and why is it proportional to the number of electrons?[J]. J Am Chem Soc， 1973 (95): 8769-8775.

[13] MAJSTOROVIC S， KLOBUCAR A， GUTMAN I. Selected topics from the theory of graph energy: Hypoenergeticgraphs[J]. Applications of Graph Spectra， 2009 (1): 65-105.

[14] LI X， MA H. All connected graphs with maximum degree at most 3 whose energies are equal to the number of vertices[J]. MATCH Commun Math Comput Chem， 2010 (64): 7-24.

[15] GONG S C， LI X， XU G H， et al. Borderenergetic graphs[J]. MATCH Commun Math Comput Chem， 2015 (74): 321-332.

[16] TURA F.L-borderenergetic graphs[J]. MATCH Commun Math Comput Chem， 2017 (77): 37-44.

[17] DENG B， LI X. More onL-borderenergetic graphs[J]. MATCH Commun Math Comput Chem， 2017 (77): 115-127.

[18] DENG B， LI X， WANG J. Further results onL-borderenergetic graphs[J]. MATCH Commun Math Comput Chem， 2017 (77): 607-616.

[19] DENG B， LI X. OnL-borderenergetic graphs with maximum degree at most 4[J]. MATCH Commun Math Comput Chem， 2018 (79): 303-310.

[20] LI X， WEI M， GONG S. A computer search for the borderenergeticgraphs of order 10[J]. MATCH Commun Math Comput Chem， 2015 (74): 333-342.

[21] SHAO Z， DENG F. Correcting the number of borderenergetic graphs of order 10[J]. MATCH Commun Math Comput Chem， 2016 (75): 263-266.

[22] DENG B， LI X， GUTMAN I. More on the borderenergetic graphs[J]. Lin Algebra Appl， 2016 (497): 199-208.

[23] HOU Y， TAO Q. Borderenergetic threshold graphs[J]. MATCH Commun Math Comput Chem， 2016 (75): 253-262.

[24] LI X， WEI M， ZHU X. Borderenergetic graphs with small maximum or large minimum degrees[J]. MATCH Commun Math Comput Chem， 2016 (77): 25-36.

[25] DAS K C， MOJALLAL S A， GUTMAN I. On Laplacian energy in terms of graph invariants[J]. Appl Math Comput， 2015 (259): 470-479.