圖能量中若干極值問(wèn)題的解決.pdf

1、用n和m分別表示一個(gè)連通簡(jiǎn)單圖G的頂點(diǎn)個(gè)數(shù)和邊數(shù)，稱c(G)=m-n+1為圖G的基本圈數(shù)。我們用圖的基本圈的個(gè)數(shù)來(lái)定義無(wú)圈、單圈，雙圈乃至k-圈圖。當(dāng)c(G)=0時(shí)，稱G為無(wú)圈圖或樹(shù)。當(dāng)c(G)=1時(shí)，稱G為單圈圖。類似地，當(dāng)c(V)=k時(shí)，稱G為k-圈圖。
　　 對(duì)給定簡(jiǎn)單圖G，用A(G)表示它的鄰接矩陣。圖G的能量定義為它的鄰接矩陣A(G)的所有特征值的絕對(duì)值之和。這一定義的重要化學(xué)背景是圖的特征值與共軛碳?xì)浠衔镏?-電子

2、的分子軌道能量級(jí)有著緊密的對(duì)應(yīng)。事實(shí)上，這一定義來(lái)自于對(duì)全開(kāi)-電子能量的Hiickel分子軌道近似。1940年，Coulson等人在研究化學(xué)分子能量時(shí)對(duì)這一事實(shí)就有了一些認(rèn)識(shí)和結(jié)論。1978年，Gutman在之前工作的基礎(chǔ)上，正式提出了圖的能量的（數(shù)學(xué)）概念，這一概念不僅適用于分子圖，也適用于一般圖。
　　 1977年，Gutman首先定義了二部圖的擬序關(guān)系。利用圖的擬序關(guān)系可以有效地解決關(guān)于圖極值能量的很多問(wèn)題，并且一直以來(lái)這

3、都是解決此類問(wèn)題的主要方法。然而，隨著研究的不斷深入，逐漸出現(xiàn)了一大批用擬序關(guān)系不能解決的能量的極值問(wèn)題，我們稱之為擬序不可比問(wèn)題。長(zhǎng)期以來(lái)，人們一直試圖去攻克這些擬序不可比問(wèn)題。最近，我們找到了一種處理這類問(wèn)題的有效方法。運(yùn)用了分析、代數(shù)和組合方法，同時(shí)主要依據(jù)能量的Coulson積分公式，我們成功地解決了這一系列長(zhǎng)期未解決的極值能量問(wèn)題。
　　 1999年，Zhang和Li在討論無(wú)圈共軛分子圖的極小能量時(shí)，發(fā)現(xiàn)在具有完美匹配

4、的樹(shù)中，具有第三極小能量的樹(shù)是兩個(gè)擬序不可比的圖之一．在2.1節(jié)，我們?cè)谇叭斯ぷ鞯幕A(chǔ)上，完全解決了這一問(wèn)題，并確定了第三到第六極小能量圖。
　　 2008年，Gutmaa等人猜想具有第四極大能量的樹(shù)是圖R(2，6，n-9)，它由從唯一的一個(gè)三度點(diǎn)出發(fā)的三條內(nèi)部不交的懸掛路構(gòu)成，這三條路的長(zhǎng)度分別為2，6和n-9。2009年，Shao和Li等人用擬序關(guān)系和圖運(yùn)算的方法得到第四極大能量樹(shù)是R(2，6，n-9)或者瓦(2，212，2

5、)，后者表示在n-8個(gè)頂點(diǎn)的路的每個(gè)端點(diǎn)上分別粘接兩條長(zhǎng)為2的懸掛路所得到的圖。然而，這兩個(gè)圖也無(wú)法用擬序來(lái)比較。在2.2節(jié)，我們研究了此問(wèn)題并確定了第四極大能量樹(shù)。
　　 2007年，Hua和Wang研究了有固定懸掛點(diǎn)數(shù)目的單圈圖，發(fā)現(xiàn)其中具有極小能量的圖在某些情況下同樣需要在兩個(gè)擬序不可比圖中選擇。在3.1節(jié)，我們完全確定了此情況下具有極小能量的圖。
　　 1999年，Caporossi，Cvetkovic，Gutm

6、an和Hansen等人猜想，對(duì)n個(gè)頂點(diǎn)的單圈圖，當(dāng)n<7或者n=9，10，11，13，15時(shí)，圈Gn具有極大能量；對(duì)其余的n，圖具有極大能量，其中P6n是由一條n-5個(gè)頂點(diǎn)的路的一個(gè)端點(diǎn)粘接一個(gè)圈所得到的。對(duì)于單圈二部圖的情況，2002年，Hou，Gutman和Woo等人利用擬序關(guān)系的方法證明具有極大能量的n階單圈二部圖是G或者，但他們不能確定到底是哪個(gè)圖達(dá)到極大能量，因?yàn)檫@兩個(gè)圖是擬序不可比的。在3.2節(jié)，我們完全確定了單圈二部圖中的