三條路并的極值能量及一類圖的能量排序

葛云鵬，火博豐，王春云，刁強強

（青海師范大學數學系，青海 西寧810008）

三條路并的極值能量及一類圖的能量排序

葛云鵬，火博豐，王春云，刁強強

（青海師范大學數學系，青海 西寧810008）

擬序是圖能量排序中一種有效方法，基于該方法，已經得到了大量圖類的極值能量排序的結果.Gutman給出了點數和為n的兩條路的并的能量排序，而三條路的并的能量排序沒有一個理想的結論.本文利用擬序法給出點數和為n的三條路的并的極值能量及一類圖能量的排序.

圖能量；三條路的并；排序；擬序

1 引言

在化學圖論中，化學分子圖的能量可以反映圖所對應的共軛分子化合物的熱力學穩定性.圖的能量越大（?。鄳衔锏臒崃W穩定性越強（弱）.基于圖能量的實際意義和理論價值，研究圖的能量排序和極值能量有十分重要的意義.一些具體的結果可以參看文獻［1-6］.

圖能量排序中路并的排序是最重要的排序之一.Gutman在文獻［7］中已經給出了點數和為的兩條路的并的能量排序，利用他的這一結論，解決了大量圖能量的排序，參看文獻［8］.對點數和為n的三條路的并的能量排序，一直沒有結論，本文利用擬序法給出點數和為n的三條路的并的極值能量及一類圖能量的排序.

設G為n階無向簡單圖，n階方陣A（G）是G的鄰接矩陣.G的特征多項式為：

這里I表示n階單位矩陣.λ1，λ1，···，λn為?（G，x）的特征根.文獻［9］給出了G的能量定義

引理1.1［10］若n1階圖G1與n2階圖G2不相交，記G1和G2的并圖為G1∪G2，則有

引理1.2［7］令n=4k，4k+1，4k+2，4k+3，則

頂點數和為n的三條路的并記為Pi∪Pj∪Pn-i-j（i≤j≤n-i-j），根據最短路Pi可將三條路的并劃分為若干類Ai=｛Pi∪Pj∪Pn-i-j，i≤j≤n-i-j｝，其中1≤i≤[n/3].

注1.1為方便起見，對于頂點數為n的路Pn，如果n為偶數，則稱路Pn為偶的，否則稱其為奇的.

引理1.3頂點數和為n的三條路的并集Ai中：

證明 由引理1.1及引理1.2可知結論成立.

引理1.4三個相鄰的集合Ai-1，Ai，Ai+1中：

a.當i為偶數時，若i≥2，有

即對于相鄰的集合，以偶數為最短路的集合中的最大能量大于以奇數為最短路的集合中的最大能量.

b.當j為奇數時，若j≥3，有

若j=1，有

即相鄰集合中，以奇數為最短路的集合中的最小能量小于以偶數為最短路的集合中的最小能量.

2 主要結論

定理2.1三條路的并Pi∪Pj∪Pn-i-j，i≤j≤n-j-i，1≤i≤[n/3]中，當i=j時，能量排序如下：

圖2-1 三條路并Pi∪Pi∪Pn-2i的能量變化圖

通過圖像，可以更加直觀的了解Pi∪Pi∪Pn-2i，1≤i≤[n/3]的能量變化.

上述定理可以用來比較一些樹的能量，下面給出一個例子.

路Pn-i-j-k-l的一個端點分別與路Pi，Pj的懸掛點連接，另一端點與路Pk，Pl的懸掛點分別連接，稱為四叉樹，記為H（i，j，k，l），如圖2-2.

圖2-2 四叉樹H（i，j，k，l）

特別地，四叉樹H（i，j，k，n-i-j-k-2）為路P2的一個端點分別與路Pi，Pj的懸掛點連接，另一端點與路Pk，Pn-i-j-k-2的懸掛點分別連接（1≤i≤（n-3）/3）.如圖2-3所示：

圖2-3 四叉樹H（i，j，k，n-i-j-k-2）

推論2.2如圖2-4，在四叉樹H（1，i，i，n-2i-3）中能量可排序為：

圖2-4 四叉樹H（1，i，i，n-2i-3）

圖2-5 三條路并Pi∪Pj∪Pj的能量變化圖

定理2.3頂點和為n的三條路并Pi∪Pj∪Pj中：

即當頂點總數n為奇數，j為奇數時，隨著j的增大，能量相應減??；j為偶數時，隨著j的增大，能量相應減小.

當頂點總數n為偶數，j為奇數時，隨著j的增大，能量相應增大.j為偶數時，隨著j的增大，能量相應增大.

定理2.4兩個相鄰的集合Ai，Ai+1中元素的排序：

綜上所述，相鄰兩個集合類中元素，最短路為奇數的三條路并的能量均小于最短路為偶數的三條路并的能量.

定理2.5頂點數和為n的三條路的并Pi∪Pj∪Pn-i-j中，

分別具有最大，次大，第三大能量；

分別具有最小，次小，第三小能量，其中i≤j≤n-i-j，1≤i≤[n/3].

猜想1最短路為偶數的三條路并的能量大多數大于最短路為奇數的三條路并的能量，但是也會有最短路為奇數的大于偶數的，參見圖2-6（a），圖2-6（b）.

圖2-6 三條路并的能量變化圖

［1］Huo B，Li X，Shi Y，etal.Determining the conjugated trees with the third-through the six-minimal energies［J］.Match Commun.Math.Comput.Chem，2011，65：521-532.

［2］Huo B，Li X，Shi Y.Complete solution to a conjecture on the maximal energy of unicyclic graphs［J］.Eur. J.Comb，2011，32：662-673.

［3］Li H.On minimal energy ordering of acyclic conjugated molecules［J］.Math.Chem，1999，25：145-169.

［4］Guo J.On the minimal energy ordering of trees with perfect matchings［J］.Discr.Appl.Math，2008，156：2598-2605.

［5］Ou J.On ordering chemical trees by energy［J］.Match Commun.Math.Comput.Chem，2010，64：157-168.

［6］Wang W，Kang L.Ordering of the trees with a perfect matching by minimal energies［J］.Lin.Algebra Appl，2009，431：946-961.

［7］Gutman I，Polansky O E.Mathematical Concepts in Organic Chemistry［M］.Berlin：Springer-Verlag，1986.

［8］Li X，Y.Shi T，Gutman I.Graph Energy［M］.New York：springer，2012.

［9］Gutman I.The Energy of a Graph：Old and New Results，in：A.Betten，A.Kohnert，R.Laue，A.Wassermann（Eds.），Algebraic Combinatorics and Applications［M］.Berlin：Springer-Verlag，2001.

［10］Cvetkovic D，Rowlinson P，Simic S.An Introduction to the Theory of Graph Spectra：London Mathematical Society Student Texts［M］.London：Cambridge Univ Pr Cambridge University Press，2010.

The union of three paths′extreme energy and energy ordering of a class of graphs

Ge Yunpeng，Huo Bofeng，Wang Chunyun，Diao Qiangqiang
（Qinghai Normal University，Qinghai，xining 810008，China）

Quasi-order can effectively solve many problems for extreme energy.Based on this method，many results for extreme energy ordering have been determined.Gutman has given the ordering for the union of two paths′energy，but there is not a good conclusion for the union of three paths′energy ordering，this paper determined the union of three paths′extreme energy by quasi-order method and given the energy ordering of a class of graphs.

graph energy，three paths union，ordering，quasi-order

O157.5

A

1008-5513（2015）04-0387-16

10.3969/j.issn.1008-5513.2015.04.008

2015-04-10.

國家自然科學基金（11261047）.

葛云鵬（1990-），碩士生，研究方向：模糊數學理論與計算.

2010 MSC:05C50