具有最小能量的四葉圖

車(chē) 雨 紅

(渭南師范學(xué)院 數(shù)理學(xué)院，陜西 渭南 714099)

?

具有最小能量的四葉圖

車(chē) 雨 紅

(渭南師范學(xué)院 數(shù)理學(xué)院，陜西 渭南 714099)

摘要：為了探討具有最小能量值的問(wèn)題，依據(jù)圖的能量理論，采用了圖解式的方法，研究了n階四葉圖之間的兩種能量變換關(guān)系，證得當(dāng)T?Sk,k≥2時(shí)的四葉圖具有最小能量的結(jié)論。圖的能量是圖的鄰接矩陣的所有特征值的絕對(duì)值之和，記為E(G)。如果圖中有一塊是樹(shù)，其他塊是圈，且所有的圈都粘在這棵樹(shù)的根節(jié)點(diǎn)上，則稱(chēng)圖是仙人掌圖，記為G，用G(n,r)表示具有r個(gè)圈的n階仙人掌圖集。當(dāng)r=4且每個(gè)圈為三角形時(shí)，稱(chēng)圖為四葉圖，記為·T。通過(guò)計(jì)算它們各自的特征多項(xiàng)式的系數(shù)，且對(duì)其進(jìn)行比較，找出了具有最小能量的四葉圖，并對(duì)所得結(jié)果進(jìn)行了驗(yàn)證。

關(guān)鍵詞：圖的能量；仙人掌圖；四葉圖；變換關(guān)系

0引言

圖是圖論的基本研究對(duì)象，此概念從一開(kāi)始出現(xiàn)就與分子圖具有密切的聯(lián)系。在化學(xué)圖論中，用一個(gè)圖來(lái)描述分子的拓?fù)浣Y(jié)構(gòu)。我們用頂點(diǎn)表示原子，邊表示化學(xué)鍵，稱(chēng)它為分子圖。在考慮飽和及共軛的碳?xì)浠衔飼r(shí)，頂點(diǎn)只代表碳原子而忽略氫原子，邊只代表碳-碳原子之間的化學(xué)鍵，這種圖叫做分子骨架圖。分子圖表達(dá)了分子的拓?fù)湫再|(zhì)，即如果兩個(gè)分子具有相同的分子圖，那么就可以說(shuō)這兩個(gè)分子具有相同的拓?fù)湫再|(zhì)。許多學(xué)者已經(jīng)得到了很多漂亮的結(jié)果，文獻(xiàn)[1]表明圖的研究與化學(xué)建立了新的聯(lián)系，人們發(fā)現(xiàn)Hückel分子軌道(HMO)理論與圖的譜之間存在明確的對(duì)應(yīng)關(guān)系，為許多代數(shù)圖論的結(jié)果提供了實(shí)際背景；文獻(xiàn)[2]將HMO意義下定義的能量E(G)推廣到任意圖G的能量；文獻(xiàn)[3]解釋了分子的結(jié)構(gòu)和性質(zhì)之間的關(guān)系；文獻(xiàn)[4]得到，相比較而言，HMO總的π-電子能量對(duì)于共軛化合物的能量估計(jì)是相當(dāng)好的；文獻(xiàn)[5-9]給出了目前圖的能量問(wèn)題的其他重要研究成果。

本文在對(duì)國(guó)內(nèi)外參考文獻(xiàn)進(jìn)行詳細(xì)了解和調(diào)查的基礎(chǔ)上，主要討論了n階四葉圖之間的兩種能量變換關(guān)系，證得當(dāng)T?Sk,k≥2時(shí)的四葉圖具有最小能量的結(jié)論，解決了對(duì)給定頂點(diǎn)數(shù)和邊數(shù)的連通圖中，具有最小能量的圖的問(wèn)題。

1基礎(chǔ)知識(shí)

1.1Coulson能量積分公式

有關(guān)圖G的能量，最著名的是Coulson公式：

(1)

對(duì)于0≤i≤[n/2]，令b2i(G)=|(-1)ia2i|，b2i+1(G)=|(-1)ia2i+1|。顯然，b0=1，b1等于圖G的邊數(shù)。根據(jù)(1)式，對(duì)于0≤i≤[n/2]，E(G)是關(guān)于bi(G)的嚴(yán)格單調(diào)函數(shù)。如果任意圖G1、G2，對(duì)于0≤i≤[n/2]，都有bi(G1)≥bi(G2)，則可稱(chēng)圖G1不小于圖G2，記作G1≥G2，或者G2≤G1。進(jìn)一步地，如果對(duì)于某個(gè)j，使得bj(G1)>bj(G2)，我們就記G1?G2。由(1)式，對(duì)于任意圖G1、G2，有

G1≥G2?E(G1)≥E(G2),G1?G2?E(G1)>E(G2)。

(2)

關(guān)于E(G)的其他結(jié)論可參見(jiàn)文獻(xiàn)[3-9]。

1.2四葉圖的定義

如果G1、G2、G3都是n階四葉圖，則定義變換I和變換II，如圖2和圖3所示。主要討論的是四葉圖在這兩種變換下能量的變化關(guān)系。

圖1　G與

圖2　變換I

圖3　變換II

2基本引理

記圖G的K匹配數(shù)目為m(G,k)，即G中k條互不相鄰的邊數(shù)。對(duì)于任意圖G,m(G,1)=G的邊數(shù)，規(guī)定m(G,0)=1。因?yàn)閗-匹配恰好關(guān)聯(lián)2k個(gè)頂點(diǎn)，所以當(dāng)2k>n時(shí)，m(G,k)=0。

引理1[3]如果G是n個(gè)頂點(diǎn)的簡(jiǎn)單圖，uv為圖G的懸掛邊，其中v為懸掛頂點(diǎn)，則對(duì)于2≤k≤n，都有

m(G,k)=m(G-v,k)+m(G-u-v,k-1)。

(3)

其中：G-v表示圖G刪掉點(diǎn)v以及與點(diǎn)v相關(guān)聯(lián)的邊剩下的圖，圖G-u-v表示圖G刪掉點(diǎn)v、點(diǎn)u及與其相關(guān)聯(lián)的邊剩下的圖。

(4)

其中：Li表示圖G中頂點(diǎn)數(shù)為i的Sach圖，即所有分支要么為K2，要么為圈的圖，p(S)表示圖S的連通分支個(gè)數(shù)，c(S)表示圖S中所含圈的個(gè)數(shù)，a0=1。

3主要結(jié)論

定理1設(shè)G∈{G1,G2,G3}為n階四葉圖，則

(1)當(dāng)i=2k時(shí)，有b2k=|a2k|=m(G,k)；

(2)當(dāng)i=2k+1時(shí)，有b2k+1=|a2k+1|=8m(G-G3,k-1)。

證明因?yàn)閳DG中的每個(gè)圈均為三角形，則所有的Li的分支或是C3∪sK2,s≥0，或是全為tK2,t≥1。

(1) 若i=2k，根據(jù)Sach定理，Li的分支中不存在C3,即Li的分支全為K2。又由圖的連通分支的定義有，每個(gè)Li的分支中的K2都是互不相鄰的，結(jié)合匹配的定義，每個(gè)Li分支的K2的邊集就相當(dāng)于G的一個(gè)k-匹配。

(2)若i=2k+1，根據(jù)Sach定理，Li的分支中存在唯一的G3，剩下的分支為K2。即Li=C3∪sK2。同理可證，a2k+1=8(-1)km(G-C3,k-1)，從而有b2k+1=|a2k+1|=8m(G-C3,k-1)，其中圖G-C3表示圖G刪掉圈C3及與C3中的頂點(diǎn)相連的邊剩下的圖。

定理2如果圖G2是圖G1通過(guò)變換I得到的四葉圖，則E(G1)

證明由引理2和定理1可以得到圖G1的各項(xiàng)系數(shù)如下：

a1=0,a2=-m(G1,1)=-n-3,a3=-8m(G1-C3,0)=-8,a4=m(G1,2)=4n-6,

a5=8m(G1-C3,1)=24,a6=-m(G1,3)=26-6n,a7=-8m(G1-C3,2)=-24,

a8=m(G1,4)=4n-27,a9=8m(G1-C3,3)=8,a10=-m(G1,5)=9-n,a11=0,a12=0。

同時(shí)可以得到圖G2的各項(xiàng)系數(shù)如下：

c1=0,c2=-m(G2,1)=-n-3,c3=-8m(G2-C3,0)=-8,

c4=m(G2,2)=12n-86,c5=8m(G2-C3,1)=8n-56，

c6=-m(G2,3)=266-30n,c7=-8m(G2-C3,2)=216-24n,

c8=m(G2,4)=28n-267,c9=8m(G2-C3,3)=24n-232,

c10=-m(G2,5)=89-9n,c11=-8m(G2-C3,4)=80-8n,c12=0。

所以可得到G1、G2的特征多項(xiàng)式如下：

Φ(G1,λ)=λn-(n+3)λn-2-8λn-3+(4n-6)λn-4+24λn-5+(26-6n)λn-6-24λn-7+(4n-27)λn-8+8λn-9+

(9-n)λn-10，

Φ(G2,λ)=λn-(n+3)λn-2-8λn-3+(12n-86)λn-4+(8n-56)λn-5+(266-30n)λn-6+(216-24n)λn-7+

(28n-267)λn-8+(24n-232)λn-9+(89-9n)λn-10+(80-80n)λn-11。

由Coulson能量公式，對(duì)圖G1，可設(shè)函數(shù)

f1(x)=[1+(n+3)x2+(4n-6)x4+(6n-26)x6+(4n-27)x8+(n-9)x10]2+(8x3+24x5+24x7+8x9)2。

對(duì)圖G2,可設(shè)函數(shù)

f2(x)=[1+(n+3)x2+(12n-86)x4+(3n-266)x6+(28n-267)x8+(9n-89)x10]2+

[8x3+(8n-56)x5+(24n-216)x7+(24n-232)x9+(80n-80)x11]2。

結(jié)合引理2及定理1有

又設(shè),

F(x)=f1(x)-f2(x)=(-64n2+1 280n-6 400)x22+(-464n2+9 136n-44 960)x20+

(-1 456n2+28 096n-135 360)x18+(-2 576n2+48 384n-226 240)x16+

(-2 800n2+50 624n-226 240)x14+(-1 940n2+32 480n-134 400)x12+

(-784n2+12 096n-42 560)x10+(-176n2+2 176n-4 160)x8+

(-16n2+64n+960)x6+(160-16n)x4，

由初等函數(shù)的性質(zhì),當(dāng)n≥11時(shí),多項(xiàng)式F(x)的每項(xiàng)系數(shù)對(duì)于n都小于0,則有F(x)<0(x>0)。從而,可得E(G1)

定理3如果圖G3是圖G1通過(guò)變換II得到的四葉圖,則E(G1)

證明由引理2和定理1可以得到圖G3的各項(xiàng)系數(shù)如下:

d1=0,d2=-m(G3,1)=-n-3，d3=-8m(G3-C3,0)=-8,d4=m(G3,2)=5n-9,

d5=8m(G3-C3,1)=32,d6=-m(G3,3)=46-10n,d7=-8m(G3-C3,2)=-48,

d8=m(G3,4)=10n-69,d9=8m(G3-C3,3)=32,d10=-m(G3,5)=45-5n,

d11=-8m(G3-C3,4)=-8,d12=0。

所以可得到G3的特征多項(xiàng)式如下:

Φ(G3,λ)=λn-(n+3)λn-2-8λn-3+(5n-9)λn-4+32λn-5+(46-10n)λn-6-48λn-7+(10n-69)λn-8+

32λn-9+(45-5n)λn-10-8λn-11+(n-11)λn-12。

對(duì)圖G3,可設(shè),

f3(x)=[1+(n+3)x2+(5n-9)x4+(10n-46)x6+(10n-69)x8+(5n-45)x10+(n-11)x12]2+

(8x3+32x5+48x7+32x9+8x11)2。

由引理2及定理1有

再設(shè)

H(x)=f1(x)-f3(x)=(-n2+22n-121)x24+(-10n2+200n-1 054)x22+

(-44n2+790n-3 974)x20+(-112n2+1 776n-8 464)x18+

(-182n2+2 492n-11 102)x16+(-196n2+2 240n-9 100)x14+

(-140n2+1 260n-4 424)x12+(-64n2+400n-1 024)x10+

(-17n2+46n+31)x8+(-2n2-8n+58)x6+(6-2n)x4。

同理,可得H(x)<0(x>0)。從而,可得E(G1)

推論1如果圖G為圖1中的n階四葉圖且T≌Sk,n≥11,k≥2,則此圖具有最小能量。

4結(jié)論驗(yàn)證

分別計(jì)算當(dāng)n=12,13,…，20時(shí)，圖G1、G2、G3的能量值如表1所示。

表1　圖G1、G2、G3在n取不同值時(shí)的能量

用Matlab繪制圖G1、G2、G3在n取不同值時(shí)能量的變化曲線(xiàn)，如圖4所示。

圖4　圖G1、G2、G3在n取不同值時(shí)的能量大小對(duì)比

由圖4可以清楚地看到，在n取不同值時(shí)，圖G1始終具有最小能量。

參考文獻(xiàn)：

[1] 張?；?圖依能量的排序[J].廈門(mén)大學(xué)學(xué)報(bào),2001,40(2):157-162.

[2] Gutman I.Advance in the Theory of Benzenoid Hydrocarbons[J].Topics Curr Chem,1992,153(2):80-88.

[3] YAN Weigan,YE Luzhen.On the maximal energy and the Hosoya indexof a type of trees with many pendent vertices[J].Match Commun Math Comput Chem,2005,53(2):449-459.

[4] HUA Hongbo,WANG Maolin.Unicyclic graphs with given number of pendent vertices and minimal energy[J].Linear Algera and its Application,2007,426(2-3):478-489.

[5] CHEN Ailian,AN Chang,Wai C S.Energy ordering of unicycle graphs[J].Match Commun Math Comput Chem,2006,55(1):95-102.

[6] ZHOU Bo,LI Feng.On the minimal energy of trees of a prescribed diameter[J].Journal of Mathematics Chemistry,2006,39(3-4):465-473.

[7] YE Luzhen,CHEN Rongsi.Ordering of trees with a given bipartition by their 7 energies and hosoya indices[J].Match Commun Math Comput Chem,2004,52:193-208.

[8] YU Aimei,LU Xuezheng.Minimum energy on tree with k-pendent vertices[J].Linear Algera and its Application,2006,418(2):625-633.

[9] LI Xueliang,SHIYongtang,Gutman I.Graph Energy[M].New York:Springer, 2012.50-55.

【責(zé)任編輯牛懷崗】

The Four-leaf Graphs with Minimum Energy

CHE Yu-hong

(School of Mathematics and Physics, Weinan Normal University, Weinan 714099, China)

Abstract:In order to discuss issues with least energy, according to the figure of the theory of energy, using the diagram type, the paper studies the two transformation relations between the four-leaf graphs with n vertices and proves that the four-leaf graphs have minimum energy whenT?Sk,k≥2. The energy of a graph is defined as the sum of absolute values of eigenvalues of the adjacent matrix, and it can be denoted by E(G). G is called cactus graph if a part of G is a tree, others are circles and all circles are connected with the root of the tree. Let G(n, r) be the set of cactus graph with n vertices and r circles. The four-leaf graph is a cactus graph when r = 4 and every circle is triangle, and it can be denoted by ·T.By calculating and comparing their respective characteristic polynomial coefficients, it finds out the four leaf graph with the minimum energy; finally, the result is verified.

Key words:the energy of graph; cactus graph; four-leaf graph; transformation relations

作者簡(jiǎn)介：車(chē)雨紅(1982—)，女，陜西合陽(yáng)人，渭南師范學(xué)院數(shù)理學(xué)院講師，理學(xué)碩士，主要從事圖論、數(shù)論研究。

基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目：擬陣的模糊化與模糊擬陣的優(yōu)化算法研究(2014JM1026)；渭南師范學(xué)院理工類(lèi)科研項(xiàng)目：基于毛毛蟲(chóng)樹(shù)能量的渭南市能源發(fā)展問(wèn)題研究(15YKP015)

收稿日期：2015-12-24

中圖分類(lèi)號(hào)：O157.14

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-5128(2016)04-0013-05

【自然科學(xué)基礎(chǔ)理論研究】