具有給定分支數(shù)森林的最小能量圖

王文環(huán)

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

圖是圖論的基本研究對(duì)象，與分子圖有密切的聯(lián)系.從20世紀(jì)上半葉以來(lái)，圖的研究與化學(xué)建立了新的聯(lián)系，人們發(fā)現(xiàn)Hückel分子軌道理論與圖的譜之間存在明確的對(duì)應(yīng)關(guān)系［1］.

令G為具有n個(gè)頂點(diǎn)的分子圖，A(G)是其連接矩陣，G的特征多項(xiàng)式［2］為

式中，I為n階單位矩陣.記φ(G，x)=0的n個(gè)根為λ1，λ2，…，λn，即為相應(yīng)圖G的特征根.在Hückel分子軌道(Hückel molecular orbital，HMO)意義下，將圖G的能量E(G)［3］定義為

E(G)是共軛分子的一個(gè)重要參數(shù)，是共軛分子的化學(xué)結(jié)構(gòu)和熱力學(xué)穩(wěn)定性之間的橋梁.圖的能量越大(小)，相應(yīng)化合物的熱力學(xué)穩(wěn)定性越強(qiáng)(弱)［3］.因此，研究具有極值能量的圖及其排序是化學(xué)圖論中的重要課題之一［4-5］，在理論化學(xué)中具有重要的意義.關(guān)于E(G)的詳細(xì)介紹可參見(jiàn)文獻(xiàn)［3］.

令m(G，k)為圖G的k匹配數(shù)，即G中k條互不相鄰的邊的個(gè)數(shù)，其中0≤k≤［n/2］.為了方便，令m(G，0)=1.對(duì)具有n個(gè)頂點(diǎn)的森林F，其能量可以表達(dá)成下面的Coulson積分公式［3］：

由式(3)可知，E(F)是m(F，k)的單調(diào)遞增函數(shù)，其中1≤k≤［n/2］.因此，對(duì)于2個(gè)森林F1和F2， Gutman等［6-7］定義了如下擬序關(guān)系：

若F1?F2，且至少存在一個(gè)整數(shù)k，使得m(F1，k)＜m(F2，k)，則有F1?F2.若對(duì)所有 k，m(F1，k)= m(F2，k)，則F1?F2.若F1?F2和F1?F2都不成立，則稱F1和F2不可比.根據(jù)式(3)和(4)，若F1?F2，則 E(F1)≤E(F2);若 F1?F2，則 E(F1)＜E(F2).

利用上述擬序關(guān)系可得到一些無(wú)圈圖在給定頂點(diǎn)時(shí)的極值能量圖.比如，對(duì)于樹(shù)，Gutman［6］得到了前4個(gè)具有較小能量的樹(shù)和具有最大能量和次大能量的樹(shù);Li等［8］刻畫了第5小和第6小能量樹(shù); Wang等［9］得到了前9個(gè)具有較小能量的樹(shù).對(duì)具有完美匹配的樹(shù)，Zhang等［10］得到了前3個(gè)具有較小能量的樹(shù);Guo［11］刻畫了前5個(gè)具有較小能量的樹(shù); Wang等［12］得到了前11個(gè)具有較小能量的樹(shù).對(duì)給定直徑的樹(shù)，Yan等［13］得到了最小能量樹(shù);Zhou等［14］得到了第2小能量樹(shù).對(duì)具有給定懸掛頂點(diǎn)數(shù)的樹(shù)，Yu等［15］得到了最小能量樹(shù).對(duì)具有給定匹配大小的樹(shù)，候耀平［16］刻畫了最小和次小能量樹(shù).對(duì)具有給定非懸掛邊數(shù)的樹(shù)，王霄霞等［17］得到了最小和次小能量樹(shù).

記Fn，q為具有n個(gè)頂點(diǎn)和q個(gè)分支的森林的集合，其中q≥1.由于森林的每個(gè)分支是頂點(diǎn)個(gè)數(shù)不少于2的樹(shù)，因此n≥2q.特別地，當(dāng)q=1，F(xiàn)n，q為具有n個(gè)頂點(diǎn)的樹(shù)的集合.當(dāng)n和q給定時(shí)，本工作確定了Fn，q中具有最小能量的圖.

1 預(yù)備工作

為了得到本工作的結(jié)論，下面引入一些圖的定義和引理.

令Pn為具有n個(gè)頂點(diǎn)的路，sPn為s條Pn的并，其中s為不小于2的正整數(shù)，K1，n-1為具有n個(gè)頂點(diǎn)的星圖.

引理1［3］令e=uv為G中的一條邊，則有

引理2［6］令T為具有n個(gè)頂點(diǎn)的樹(shù)，當(dāng)n≥4時(shí)，有K1，n-1?T，等號(hào)成立當(dāng)且僅當(dāng)T=K1，n-1.

2 主要結(jié)果

定理1 設(shè)F∈Fn，q，其中1≤q≤n/2，且n≥4，則有E(K1，n-2q+1∪(q-1)P2)≤E(F)，等號(hào)成立當(dāng)且僅當(dāng)F=K1，n-2q+1∪(q-1)P2.

證明 當(dāng)q=1時(shí)，F(xiàn)n，q為具有n個(gè)頂點(diǎn)的樹(shù)的集合.由引理2可知，定理1成立.

當(dāng)q≥2時(shí)，由式(4)可知，只要證明

等號(hào)成立當(dāng)且僅當(dāng)F=K1，n-2q+1∪(q-1)P2.

下面對(duì)n用數(shù)學(xué)歸納法證明定理1成立.

當(dāng)n=2q和2q+1時(shí)，由于F∈Fn，q，因此，F(xiàn)分別為qP2和P3∪(q-1)P2.顯然式(6)的等號(hào)成立.

當(dāng)n=2q+k，k≥2時(shí)，設(shè)式(6)成立.

下面證明當(dāng)n=2q+k+1時(shí)，式(6)成立.

由于F∈Fn，q，令F=T1∪T2∪…∪Tq，其中Ti為頂點(diǎn)個(gè)數(shù)不少于2的樹(shù)，1≤i≤q.由于n=2q+ k+1，且k≥2，因此，在F中必有一個(gè)頂點(diǎn)個(gè)數(shù)不少于3的分支.不失一般性，假設(shè)此分支為Tq.令uv為K1，n-2q+1∪(q-1)P2中分支K1，n-2q+1的一條邊，u'v'為F中分支Tq的一條懸掛邊.由引理1，有

由于樹(shù)Tq的頂點(diǎn)個(gè)數(shù)不少于3，因此，Tq-u'v'為頂點(diǎn)個(gè)數(shù)不少于2的樹(shù).所以 T1∪T2∪…∪Tq-1∪(Tq-u'v')為具有q個(gè)分支且頂點(diǎn)數(shù)為n-1的森林.由歸納假設(shè)，有

等號(hào)成立當(dāng)且僅當(dāng)T1∪T2∪…∪Tq-1∪(Tq-u'v')= K1，n-2q∪(q-1)P2.

又由于當(dāng)1≤i≤q-1時(shí)，Ti為頂點(diǎn)個(gè)數(shù)不少于2的樹(shù)，因此，有P2?Ti.所以

式中第1個(gè)等號(hào)成立當(dāng)且僅當(dāng)對(duì)所有1≤i≤q-1，Ti=P2;第2個(gè)等號(hào)成立當(dāng)且僅當(dāng)Tq-u'-v'是孤立點(diǎn)的集合.

由式(9)和(10)，比較式(7)和(8)，當(dāng)n=2q+ k+1時(shí)，式(6)成立，且式(6)等號(hào)成立當(dāng)且僅當(dāng)式(9)和(10)中的所有等號(hào)同時(shí)成立，即Ti=P2且Tq=K1，n-2q+1，其中1≤i≤q-1.因此，定理1成立.

［1］ 張?；?圖依能量的排序［J］.廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，2001，40(2)：157-162.

［2］ CVETKOVICD M，DOOBM H S.Spectra of graphs theory and application［M］.New York：Academic Press，1980.

［3］ GUTMANI，POLANSKYO.Mathematical concepts in organic chemistry［M］.Berlin：Springer-Verlag，1986.

［4］ 唐熬慶，江元聲.分子軌道圖形理論［M］.北京：科學(xué)出版社，1980.

［5］ CAPOROSSIG，CVETKOVICD，GUTMANI.Variable neighborhood search for extremal graphs.2.finding graphs with extremal energy［J］.Journal of Chemical Information and Computer Sciences，1999，39：984-996.

［6］ GUTMANI.Acyclic systems with extremal Hückel πelectron energy［J］.Theoretica Chimica Acta，1977，45：79-87.

［7］ GUTMANI，ZHANGF.On the ordering of graphs with respect to their matching numbers［J］.Discrete Applied Mathematics，1986，15(1)：25-33.

［8］ LIN N，LIS C.On the extremal energies of trees［J］.MATCH-Communications in Mathematical and in Computer Chemistry，2008，59(2)：291-314.

［9］ WANGW H，KANGL Y.Ordering of the trees by minimal energies ［J］. Journal of Mathematical Chemistry，2010，47(3)：937-958.

［10］ ZHANGF，LIH.On acyclic conjugated molecules with minimal energies［J］.Discrete Applied Mathematics，1999，92(1)：71-84.

［11］ GUOJ M.On the minimal energy ordering of trees with perfect matchings［J］.Discrete Applied Mathematics，2008，156(14)：2598-2605.

［12］ WANGW H，KANGL Y.Ordering of the trees with a perfect matching by minimal energies［J］.Linear Algebra and Its Applications，2009，431：946-961.

［13］ YANW G，YEL Z.On the minimal energy of trees with a given diameter［J］.Applied Mathematics Letters，2005，18(9)：1046-1052.

［14］ ZHOUB，LIF.On minimal energies of trees of a prescribed diameter［J］. JournalofMathematical Chemistry，2006，39(3/4)：465-473.

［15］ YUA M，LüX Z.Minimum energy on trees with k pendent vertices ［J］. Linear Algebra and Its Applications，2006，418(2/3)：625-633.

［16］ 侯耀平.具有給定匹配大小的極小能量樹(shù)［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2003，23：491-494.

［17］ 王霄霞，郭曉峰.關(guān)于具有給定非懸掛邊數(shù)的樹(shù)的極小能量［J］.數(shù)學(xué)研究，2006，39：109-116.