邊界能量圖研究的綜述

鄧 波,李學(xué)良

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

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

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

關(guān)于圖能量及其應(yīng)用的相關(guān)內(nèi)容,可以參考文[2-5].

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

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

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

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

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

然而當(dāng)最大度Δ至多為3時(shí)，除了如下幾個(gè)特殊樹外，都不存在次能量樹.

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

圖1 樹S1,S2,S3和W

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

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

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

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

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

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

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

1 邊界能量圖的搜索與構(gòu)造

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

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

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

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

圖4 6個(gè)具有8個(gè)頂點(diǎn)的非完全邊界能量圖

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

圖5 17個(gè)具有9個(gè)頂點(diǎn)的非完全邊界能量圖

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

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

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

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

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

方式3 正則圖、補(bǔ)圖與圖的并運(yùn)算.使用正則圖及其補(bǔ)圖在圖譜上的性質(zhì)，Gong等[15]構(gòu)造出一類邊界能量圖.

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

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

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

(3)

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

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

(4)

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

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

在化學(xué)圖論中，經(jīng)常研究最大度不超過4的圖.因?yàn)檫@類圖有專門的化學(xué)應(yīng)用背景，在研究次能量圖和其他化學(xué)指標(biāo)時(shí)經(jīng)常對(duì)此類圖進(jìn)行研究[9-10,14].對(duì)邊界能量圖也存在相關(guān)結(jié)果，Li等[24]對(duì)滿足最大度不超過4的邊界能量圖的結(jié)構(gòu)性質(zhì)進(jìn)行了刻畫.

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

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

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

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

(iii)G是非偶圖;

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

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

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

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

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

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

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

4 拉普拉斯邊界能量圖

4.1 拉普拉斯邊界能量圖的構(gòu)造與搜索

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

圖的 Ferrers-Sylvester圖

圖7 門檻圖

(5)

等號(hào)成立當(dāng)且僅當(dāng)圖G是門檻圖.

(6)

由(6)，則

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

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

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

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

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

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

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

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

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

(7)

當(dāng)G是4-正則時(shí)，(7)中的界是漸進(jìn)緊的.

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

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

(8)

當(dāng)G是4-正則時(shí)，(8)中的界是漸進(jìn)緊的.

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

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

(9)

當(dāng)G是4-正則時(shí)，(9)中的界是漸進(jìn)緊的.

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

(10)

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

(11)

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

4.3 非拉普拉斯邊界能量圖

Deng等[18]陸續(xù)證明了所有的樹、圈、完全二部圖和大部分2-連通圖都不是拉普拉斯邊界能量圖.如下這類2-連通圖不是拉普拉斯邊界能量圖，令t(G)為圖G中度為3的頂點(diǎn)的個(gè)數(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 頂點(diǎn)數(shù)分別為4,6,8和滿足δ=1的拉普拉斯邊界能量圖

5 后續(xù)研究

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

[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.