王文環(huán)， 徐薇薇

(上海大學(xué)理學(xué)院，上海200444)

樹依能量的排序

王文環(huán)， 徐薇薇

(上海大學(xué)理學(xué)院，上海200444)

令Tn是頂點(diǎn)個數(shù)為n的樹的集合．已有學(xué)者針對Tn中樹依能量從小到大的排序提出了兩個猜想，其中一個猜想是Tn中兩個圖能量的比較，另一個是Tn中當(dāng)n≥7 117 599時的第10小至第12小能量樹．該文證明這兩個猜想成立;確定Tn中當(dāng)n≥7 117 599時前12個具有較小能量的樹．

樹;排序;最小能量

Abstract:Let Tnbe a set of trees with n vertices．The increasing orders in terms of the minimal energies of the trees in Tnhad been considered and two conjectures were proposed．The first one is the comparison of the energies of two graphs in Tn．The other is about the trees with the 10th to 12th minimal energies for n≥7 117 599．This paper proves that the two conjectures are true，and obtain the first 12 trees within Tnfor n≥7 117 599．

Key words:tree;ordering;minimal energy

設(shè)G為具有n個頂點(diǎn)的簡單圖．在Hückel分子軌道(Hückel molecular orbit，HMO)意義下，圖 G 的能量定義為

式中，λ1，λ2，…，λn為 φ(G，x)=0 的 n 個根，這里

為G的特征多項式［1］，I為n階單位矩陣，A(G)為G的鄰接矩陣，a0，a1，…，an為 φ(G，x)的系數(shù)．由于A(G)是對稱的，因此每個λi(1≤i≤n)是實(shí)的．

圖的能量是圖所對應(yīng)的共軛分子化學(xué)結(jié)構(gòu)和熱力學(xué)穩(wěn)定性之間的一個橋梁［2］．在化學(xué)圖論中，圖的能量越大(小)，相應(yīng)化合物的熱力學(xué)穩(wěn)定性越強(qiáng)(弱)．基于圖能量的實(shí)際意義和理論價值，在化學(xué)圖論中，研究具有極值能量的圖具有十分重要的地位和意義［3］．進(jìn)一步了解圖能量的數(shù)學(xué)概念和性質(zhì)可參見文獻(xiàn)［1-2］．

研究圖依能量排序的一個有效方法是系數(shù)比較法，即對所考慮的圖根據(jù)其特征多項式的系數(shù)絕對值的大小進(jìn)行比較［4-10］．樹是圖論中具有典型意義的一種圖類．令Tn是頂點(diǎn)個數(shù)為n的樹的集合，對Tn中樹依能量從小到大(從大到小)的排序已有一些研究結(jié)果．利用系數(shù)比較法，Gutman［4］得到了Tn中前 4個具有較小能量的樹．Li等［9］拓寬了Gutman［4］的結(jié)果，得到了 Tn中當(dāng) n≥6時的第5小能量樹，給出了Tn中當(dāng)n≥14時的第6小能量樹．但是，系數(shù)比較法具有一定的局限性，在某些情況下，對圖的能量比較失效．例如，Li等［9］就未能得到Tn中第7小能量樹．

除了系數(shù)比較法，另外一個有效的方法是利用零點(diǎn)定理來比較兩個圖的能量．因此，人們極大地拓寬了圖依能量的排序范圍［11-14］．利用上述兩種方法，對Tn中樹，當(dāng) n≥46，7 117 598≥n≥26 和25≥n≥18時，Wang等［11］分別得到了前9個、前12個和前11個具有較小能量的樹且進(jìn)行了排序;當(dāng)17≥n≥7時，Wang等［11］也得到了許多具有較小能量的樹且進(jìn)行了排序．

雖然零點(diǎn)定理可成功地用來比較兩個圖的能量，但也具有其局限性．為了克服系數(shù)比較法和零點(diǎn)定理的局限性，需要引入新的有效方法來比較圖的能量．例如，Huo等［15］發(fā)展了一種新方法，即直接從Coulson積分公式出發(fā)，利用實(shí)分析的方法比較了兩個圖的能量大?。谖墨I(xiàn)［11］中，零點(diǎn)定理不能用來比較Tn中當(dāng)n≥7 117 599時兩個候選圖的能量大?。畬Υ耍琖ang等［11］只是給出兩個猜想，其中一個是兩個候選圖能量的比較，另一個是Tn中當(dāng)n≥7 117 599時的第10小至第12小能量樹．

1 準(zhǔn)備工作

記Tn中直徑為 d的樹的集合為 Tdn，其中2≤d≤n－1．令Pn是頂點(diǎn)個數(shù)為n的路，Pn上的頂點(diǎn)依順序標(biāo)號為 v0，v1，…，vn－1．令 Tdn(n1，n2，…，nd－1)為在Pd+1上的頂點(diǎn) vi(i=1，2，…，d－1)上分別加

ni(ni≥0)條懸掛邊后得到的樹．顯然，d －1，Tdn(n1，n2，…，nd－1)∈ Tdn．T4n(n －5，0，0)，Un=T4n(n －6，0，1)，Hn=T4n(0，n －5，0)，Qn'=T4n(n －6，1，0)．

令T1和T2為Tn中的兩棵樹．為了簡單起見，引入符號“?”，“?”和“→→”如下:

當(dāng)n≥14時，Tn中前8個具有較小能量的樹為

式中等號成立當(dāng)且僅當(dāng)n=8．下面用符號(◇)來替代式(4)．式(4)中前 4 個圖由 Gutman［4］得到，第 5和第6個圖由Li等［9］得到，第7和第8個圖由Wang等［11］得到．此外，當(dāng) n≥46 時，Wang 等［11］得到了 Tn中前9個具有較小能量的樹，即(◇)?Hn?T，其中T不等于Hn和(◇)中的圖．

對于不等式中的T，假定T∈Tn且T不是不等式中已列出的圖．利用零點(diǎn)定理，Wang等［11］得到了如下引理1．

引理1 當(dāng)7 117 598≥n≥11時，Tn4(n－8，0，3)?Qn'．

在引理1的基礎(chǔ)上，當(dāng)7 117 598≥n≥59時，Wang等［11］得到了 Tn中前12個具有較小能量的樹，即有如下定理1．

定理1 令T∈Tn且7 117 598≥n≥59，則

由于零點(diǎn)定理的局限性，在引理1中，不能證明當(dāng) n≥7 117 599 時，T4n(n －8，0，3)?Qn'成立．因此，Wang等［11］給出了如下2個猜想．

猜想1 當(dāng) n≥7 117 599，T4n(n －8，0，3)?Qn'．猜想2 令T∈Tn且n≥7 117 599，則

本研究將利用根與特征多項式系數(shù)之間的關(guān)系，嚴(yán)格證明猜想1和猜想2成立，從而確定了Tn中當(dāng)n≥7 117 599時前12個具有較小能量的樹．

2 主要結(jié)果

首先證明猜想1成立，則有如下引理2．

引理2 當(dāng) n≥11 時，T4n(n－8，0，3)?Qn'．

證明 文獻(xiàn)［11］已得到

不妨令 z1＜z2＜z3．

最后，由圖能量的定義式(1)以及式(7)～(10)，可得

引理2證畢．

由文獻(xiàn)［11］和本研究的引理2，下面證明猜想2成立，則有如下定理2．

由文獻(xiàn)［11］的引理12和引理14，當(dāng) T∈{T3n(n1，n2)，T4n(n1，0，n3)}且 n≥59，其中 n2≥5，n3≥4 時，有 Qn'?T3n(n －9，5)→→T．又由文獻(xiàn)［11］的引理 19，當(dāng)T∈Tn{T3n(n1，n2)，T4n(n1，0，n3)}且 n≥59 時，有Qn'?T．因此，對于T∈Tn且T不為式(11)中所列出的圖，當(dāng) n≥59時，皆有 Qn'?T成立．顯然，由式(12)～(14)，定理2成立．

定理2拓寬了文獻(xiàn)［11］的排序范圍，當(dāng) n≥7 117 599時，得到了Tn中前12個具有較小能量的樹，比原有文獻(xiàn)多了3個．由定理1和定理2可以發(fā)現(xiàn)，Tn中當(dāng)7 117 598≥n≥59和n≥7 117 599時，前12個具有較小能量的樹及其排序是相同的，因此有如下推論1．

推論1彌補(bǔ)了定理1的不足，完全得到了Tn中當(dāng)n≥59時前12個具有較小能量的樹并進(jìn)行了排序．同時，將文獻(xiàn)［11］的排序結(jié)果進(jìn)行了推廣，使排序結(jié)果更加完滿．

［1］ CVETKOVIC D M，DOOB M，SACHS H．Spectra of graphs theory and application［M］．New York:Academic Press，1980．

［2］ GUTMAN I，POLANSKY O．Mathematical concepts in organic chemistry［M］．Berlin:Springer-Verlag，1986．

［3］ 唐熬慶．分子軌道圖形理論［M］．北京:科學(xué)出版社，1980．

［4］ GUTMAN I．Acyclic systems with extremal Hückelπelectron energy［J］．Theoretica Chimica Acta，1977，45:79-87．

［5］ ZHANG F，LI H．On acyclic conjugated molecules with minimal energies ［J］．Discrete Applied Mathematics，1999，92(1):71-84．

［6］ HOU Y P．Unicyclic graphs with minimal energy［J］．Journal of Mathematical Chemistry，2001，29(3):163-168．

［7］ ZHANG J B，ZHOU B．On bicyclic graphs with minimal energies［J］．Journal of Mathematical Chemistry，2005，37(4):423-431．

［8］ LI X L，ZHANG J B．On bicyclic graphs with maximal energy［J］．Linear Algebra and Its Applications，2007，427(1):87-98．

［9］ LI N N，LI SC．On the extremal energies of trees［J］．MATCH-Communications in Mathematical and in Computer Chemistry，2008，59(2):291-314．

［10］ LI S，LI X，ZHU Z．On tricyclic graphs with minimal energy［J］．MATCH-Communications in Mathematical and in Computer Chemistry，2008，59(2):397-419．

［11］ WANG W H，KANG L Y．Ordering of the trees by minimal energies ［J］． Journal of Mathematical Chemistry，2010，47(3):937-958．

［12］ GUO J M．On the minimal energy ordering of trees with perfect matchings［J］．Discrete Applied Mathematics，2008，156(14):2598-2605．

［13］ WANG W H，KANG L Y．Ordering of the trees with a perfect matching by minimal energies［J］．Linear Algebra and Its Applications，2009，431(5/6/7):946-961．

［14］ LIU Y．Some results on energy of unicyclic graphs with n vertices［J］．Journal of Mathematical Chemistry，2010，47(1):1-10．

［15］ HUO B F，JI SJ，LI X L．Note on unicyclic graphs with given number of pendent vertices and minimal energy［J］．Linear Algebra and Its Applications，2010，433(7):1381-1387．

Tree Ordering According to Minimal Energies

WANG Wen-huan，XU Wei-wei
(College of Sciences，Shanghai University，Shanghai 200444，China)

O 157．6

A

1007-2861(2012)05-0480-04

10．3969/j．issn．1007-2861．2012．05．008

2011-09-15

國家自然科學(xué)基金資助項目(11001166);上海市重點(diǎn)學(xué)科建設(shè)資助項目(S30104)

王文環(huán)(1975～)，女，副教授，博士，研究方向?yàn)閳D論及其應(yīng)用．E-mail:whwang@shu．edu．cn