具有最小能量的四叶图

车 雨 红

(渭南师范学院 数理学院，陕西 渭南 714099)



具有最小能量的四叶图

车 雨 红

(渭南师范学院 数理学院，陕西 渭南 714099)

摘要：为了探讨具有最小能量值的问题，依据图的能量理论，采用了图解式的方法，研究了n阶四叶图之间的两种能量变换关系，证得当T≅Sk,k≥2时的四叶图具有最小能量的结论。图的能量是图的邻接矩阵的所有特征值的绝对值之和，记为E(G)。如果图中有一块是树，其他块是圈，且所有的圈都粘在这棵树的根节点上，则称图是仙人掌图，记为G，用G(n,r)表示具有r个圈的n阶仙人掌图集。当r=4且每个圈为三角形时，称图为四叶图，记为·T。通过计算它们各自的特征多项式的系数，且对其进行比较，找出了具有最小能量的四叶图，并对所得结果进行了验证。

关键词：图的能量；仙人掌图；四叶图；变换关系

0引言

图是图论的基本研究对象，此概念从一开始出现就与分子图具有密切的联系。在化学图论中，用一个图来描述分子的拓扑结构。我们用顶点表示原子，边表示化学键，称它为分子图。在考虑饱和及共轭的碳氢化合物时，顶点只代表碳原子而忽略氢原子，边只代表碳-碳原子之间的化学键，这种图叫做分子骨架图。分子图表达了分子的拓扑性质，即如果两个分子具有相同的分子图，那么就可以说这两个分子具有相同的拓扑性质。许多学者已经得到了很多漂亮的结果，文献[1]表明图的研究与化学建立了新的联系，人们发现Hückel分子轨道(HMO)理论与图的谱之间存在明确的对应关系，为许多代数图论的结果提供了实际背景；文献[2]将HMO意义下定义的能量E(G)推广到任意图G的能量；文献[3]解释了分子的结构和性质之间的关系；文献[4]得到，相比较而言，HMO总的π-电子能量对于共轭化合物的能量估计是相当好的；文献[5-9]给出了目前图的能量问题的其他重要研究成果。

本文在对国内外参考文献进行详细了解和调查的基础上，主要讨论了n阶四叶图之间的两种能量变换关系，证得当T≅Sk,k≥2时的四叶图具有最小能量的结论，解决了对给定顶点数和边数的连通图中，具有最小能量的图的问题。

1基础知识

1.1Coulson能量积分公式

有关图G的能量，最著名的是Coulson公式：

(1)

对于0≤i≤[n/2]，令b2i(G)=|(-1)ia2i|，b2i+1(G)=|(-1)ia2i+1|。显然，b0=1，b1等于图G的边数。根据(1)式，对于0≤i≤[n/2]，E(G)是关于bi(G)的严格单调函数。如果任意图G1、G2，对于0≤i≤[n/2]，都有bi(G1)≥bi(G2)，则可称图G1不小于图G2，记作G1≥G2，或者G2≤G1。进一步地，如果对于某个j，使得bj(G1)>bj(G2)，我们就记G1≻G2。由(1)式，对于任意图G1、G2，有

G1≥G2⟺E(G1)≥E(G2),G1≻G2⟺E(G1)>E(G2)。

(2)

关于E(G)的其他结论可参见文献[3-9]。

1.2四叶图的定义

如果G1、G2、G3都是n阶四叶图，则定义变换I和变换II，如图2和图3所示。主要讨论的是四叶图在这两种变换下能量的变化关系。

图1　G与

图2　变换I

图3　变换II

2基本引理

记图G的K匹配数目为m(G,k)，即G中k条互不相邻的边数。对于任意图G,m(G,1)=G的边数，规定m(G,0)=1。因为k-匹配恰好关联2k个顶点，所以当2k>n时，m(G,k)=0。

引理1[3]如果G是n个顶点的简单图，uv为图G的悬挂边，其中v为悬挂顶点，则对于2≤k≤n，都有

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

(3)

其中：G-v表示图G删掉点v以及与点v相关联的边剩下的图，图G-u-v表示图G删掉点v、点u及与其相关联的边剩下的图。

(4)

其中：Li表示图G中顶点数为i的Sach图，即所有分支要么为K2，要么为圈的图，p(S)表示图S的连通分支个数，c(S)表示图S中所含圈的个数，a0=1。

3主要结论

定理1设G∈{G1,G2,G3}为n阶四叶图，则

(1)当i=2k时，有b2k=|a2k|=m(G,k)；

(2)当i=2k+1时，有b2k+1=|a2k+1|=8m(G-G3,k-1)。

证明因为图G中的每个圈均为三角形，则所有的Li的分支或是C3∪sK2,s≥0，或是全为tK2,t≥1。

(1) 若i=2k，根据Sach定理，Li的分支中不存在C3,即Li的分支全为K2。又由图的连通分支的定义有，每个Li的分支中的K2都是互不相邻的，结合匹配的定义，每个Li分支的K2的边集就相当于G的一个k-匹配。

(2)若i=2k+1，根据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中的顶点相连的边剩下的图。

定理2如果图G2是图G1通过变换I得到的四叶图，则E(G1)

证明由引理2和定理1可以得到图G1的各项系数如下：

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。

同时可以得到图G2的各项系数如下：

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的特征多项式如下：

Φ(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能量公式，对图G1，可设函数

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

对图G2,可设函数

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。

结合引理2及定理1有

又设,

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，

由初等函数的性质,当n≥11时,多项式F(x)的每项系数对于n都小于0,则有F(x)<0(x>0)。从而,可得E(G1)

定理3如果图G3是图G1通过变换II得到的四叶图,则E(G1)

证明由引理2和定理1可以得到图G3的各项系数如下:

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的特征多项式如下:

Φ(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。

对图G3,可设,

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有

再设

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结论验证

分别计算当n=12,13,…，20时，图G1、G2、G3的能量值如表1所示。

表1　图G1、G2、G3在n取不同值时的能量

用Matlab绘制图G1、G2、G3在n取不同值时能量的变化曲线，如图4所示。

图4　图G1、G2、G3在n取不同值时的能量大小对比

由图4可以清楚地看到，在n取不同值时，图G1始终具有最小能量。

参考文献：

[1] 张福基.图依能量的排序[J].厦门大学学报,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.

【责任编辑牛怀岗】

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

作者简介：车雨红(1982—)，女，陕西合阳人，渭南师范学院数理学院讲师，理学硕士，主要从事图论、数论研究。

基金项目：陕西省自然科学基金资助项目：拟阵的模糊化与模糊拟阵的优化算法研究(2014JM1026)；渭南师范学院理工类科研项目：基于毛毛虫树能量的渭南市能源发展问题研究(15YKP015)

收稿日期：2015-12-24

中图分类号：O157.14

文献标志码：A

文章编号：1009-5128(2016)04-0013-05

【自然科学基础理论研究】