圖能量中若干極值問題的解決.pdf

1、用n和m分別表示一個連通簡單圖G的頂點個數和邊數，稱c(G)=m-n+1為圖G的基本圈數。我們用圖的基本圈的個數來定義無圈、單圈，雙圈乃至k-圈圖。當c(G)=0時，稱G為無圈圖或樹。當c(G)=1時，稱G為單圈圖。類似地，當c(V)=k時，稱G為k-圈圖。
　　 對給定簡單圖G，用A(G)表示它的鄰接矩陣。圖G的能量定義為它的鄰接矩陣A(G)的所有特征值的絕對值之和。這一定義的重要化學背景是圖的特征值與共軛碳氫化合物中7-電子

2、的分子軌道能量級有著緊密的對應。事實上，這一定義來自于對全開-電子能量的Hiickel分子軌道近似。1940年，Coulson等人在研究化學分子能量時對這一事實就有了一些認識和結論。1978年，Gutman在之前工作的基礎上，正式提出了圖的能量的（數學）概念，這一概念不僅適用于分子圖，也適用于一般圖。
　　 1977年，Gutman首先定義了二部圖的擬序關系。利用圖的擬序關系可以有效地解決關于圖極值能量的很多問題，并且一直以來這

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

4、的樹中，具有第三極小能量的樹是兩個擬序不可比的圖之一．在2.1節(jié)，我們在前人工作的基礎上，完全解決了這一問題，并確定了第三到第六極小能量圖。
　　 2008年，Gutmaa等人猜想具有第四極大能量的樹是圖R(2，6，n-9)，它由從唯一的一個三度點出發(fā)的三條內部不交的懸掛路構成，這三條路的長度分別為2，6和n-9。2009年，Shao和Li等人用擬序關系和圖運算的方法得到第四極大能量樹是R(2，6，n-9)或者瓦(2，212，2

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

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