心形图的匹配能序及Hosoya指标排序

2019-06-24 06:10吴量刘小花汪一航
纯粹数学与应用数学 2019年1期
关键词:心形能级结论

吴量,刘小花,汪一航

(1.宁波大学理学院,浙江 宁波 315211;2.青海民族大学数学与统计学院,青海 西宁 810007)

1 引言

本文仅考虑有限无向的简单图.设一个图G=(V,E)是n个点的连通图,其中V是非空的顶点集,E是非空边集,且A(G)是G的邻接矩阵,图G的特征多项式Φ(G)在文献[1]中被定义为:这里I是n个点的恒等矩阵.等式 Φ(G)=0的根λ1,λ2,···,λn称为A(G)的特征根.G的能级E(G)被定义为A(G)的特征根的绝对值的和,记为能级定义自1978年被提出以来,前人已做了大量的研究,许多成果层出不穷,参看专著[4].

设G是n个点的图,所谓G的一个匹配是指的一个生成子图,它的每个分支或是孤立点或是孤立边.恰有k条边的匹配称为k-匹配.在文献[1]中匹配多项式定义为:

这里m(G,k)是G中的k-匹配的数目.为了方便,本文中将µ(G,x)简记为µ(G).

匹配多项式是一种计数多项式,它在数学,统计物理和化学都有着很重要的应用.在统计物理上,匹配多项式是描述一种物理系统的数学模型,物理学家Heilmann和Lieb为了研究此物理系统引进了图的二元匹配多项式,见文献[2].在理论化学中,它的系数的绝对值的和(即所有的匹配总数)就是这个图所表示的碳氢化合物的Hosoya指标,记为该指标与这个化合物的沸点有关,参看文献[3].匹配多项式的根的绝对值的和称为图的匹配能级,它与这个图所表示的芳香烃的活性有关,见文献[5].文献[8]也提到匹配能级是一个与化学应用相关的量,得出了一个简单的关系:TRE(G)=E(G)−ME(G),这里TRE(G)被称作拓扑共振能量.关于匹配能级的化学应用,详细信息见文献[7].前人对图的能级已经有了大量的研究,然而,对图的匹配能级的研究较为少见.

以Pn,Cn,Kn,Tn分别表示n个点的路、圈、完全图和树.以G∪H表示两个图G和G的并图.把形似“心”的图称为心形图,它是路Pa+2的首尾两个点与圈C4的某条边的两个端点分别粘结在一起,且路Pb+2的首尾两个点与它的相邻边的两个端点互相粘结,所得到的图称为心形图,记为G(a,4,b)(a≥1,b≥1),(见图1).在这篇文章中得到了心形图之间的匹配能序以及他们的Hosoya指标排序.

图1 心形图G(a,4,b)(a≥1,b≥1)

2 若干引理

引理2.1[1]设图G有k个连通分支,µ(Gi)表示第i个分支图的匹配多项式,则

引理2.2[1]设G是一个图,e=uv∈E(G),则

这里µ(Gu,x),µ(G{u,i},x)分别表示从图G中删去点u所得到的图的匹配多项式,从图G中删去点u和点i(这里的i表示与u相关联的点)所得到的图的匹配多项式.

(2)µ(G,x)=µ(G−e,x)−µ(G{u,v},x).

这里µ(G−e,x),µ(G{u,v},x)分别表示从图G中删去边e所得到的图的匹配多项式,从图G中删去点u和点v所得到的图的匹配多项式.

引理2.3设Pn是n个点的路,则

证明由引理2.2和引理2.1,显然.

引理2.4设Pn是n个点的路,k是下面有意义的整数,则

证明由引理2.3知,

引理2.5[3]设G是一个图,则,这里m(G,k)是G中的k-匹配的数目,k=0,1,2,···.

由引理 2.5和对数函数的单调性,规定一种偏序关系 “≺”.设G1,G2是两个n阶图,由引理 2.5的单调性,对所有的非负整数k,若满足m(G1,k)≤m(G2,k),则G1≼G2.进一步,如果不等式m(G1,k)

引理2.6[7]设G1,G2是两个n阶图,如果存在一个m阶图H,满足

则:(1)n−m是一个偶数;(2)如果n−m≡0(mod 4),则ME(G1)>ME(G2);(3)如果n−m≡2(mod 4),则ME(G1)

3 主要定理及证明

定理3.1 设G(a,4,b)(a≥1,b≥1)是a+4+b个点的图,则

(1)当a+b=4k时,

(2)当a+b=4k+1时,

(3)当a+b=4k+2时,

(4)当a+b=4k+3时,

证明由引理2.1,两次运用删边的方法,分别删去图1中的e1,e2,得

同理,

则有

由引理2.3,引理2.4可以推得上式.

(1)当a+b=4k时,

(i)当取a=2l,b=4k−2l(2≤l≤k)时,

由引理2.6的(1)得,

(ii)当取a=2l,b=4k−2l(l=k)时,

由引理2.6的(2)得,

(iii)当取a=2l−1,b=4k−2l+1(2≤l≤k)时,

由引理2.6的(2)得,

(2)当a+b=4k+1时,

(i)证明当2≤l≤k时,

与 (1)的(i)类似,当2≤l≤k时,只需取a=2l,b=4k−2l+1,

由引理2.6的(1)得,结论成立.

(ii)证明

与(1)的(ii)类似,只需取a=2k,b=2k+1,(l=k),

由引理2.6的(2)得,结论成立.

(iii)证明当2≤l≤k时,

与(1)的(iii)类似,当2≤l≤k时,只需取a=2l−1,b=4k−2l+2,

由引理2.6的(2)得,结论成立.

(3)当a+b=4k+2时,

(i)证明当2≤l≤k时,ME(G(2l−2,4,4k−2l+4))>ME(G(2l,4,4k−2l+2)).

与(1)的(i)类似,当2≤l≤k时,只需取a=2l,b=4k−2l+2,

由引理2.6的(1)得,结论成立.

(ii)ME(G(2k,4,2k+2))>ME(G(2k+1,4,2k+1)).

事实上,与 (1)的(ii)类似,只需取a=2k+1,b=2k+1(l=k),

由引理2.6的(2)得,结论成立.

(iii)证明当2≤l≤k时,

与 (1)的(iii)类似,当2≤l≤k时,只需取a=2l+1,b=4k−2l+1,

由引理2.6的(2)得,结论成立.

(4)当a+b=4k+3时,

(i)证明当2≤l≤k时,

与 (1)的(i)类似,当2≤l≤k时,只需取a=2l,b=4k−2l+3,

由引理2.6的(1)得,结论成立.

(ii)证明ME(G(2k,4,2k+3))>ME(G(2k+1,4,2k+2)).

与 (1)的(ii)类似,只需取a=2k+1,b=2k+2,

由引理2.6的(1)得,结论成立.

(iii)证明当2≤l≤k时,ME(G(2l+1,4,4k−2l+2))>ME(G(2l−1,4,4k−2l+4)).

与 (1)的(iii)类似,当2≤l≤k时,只需取a=2l+1,b=4k−2l+2,

由引理2.6的(2)得,结论成立.

由引理2.5的积分公式,根据对数函数的单调性,很明显可以看出,G的匹配能级随着m(G,k)单调递增,再由Hosoya指标的定义及定理3.1容易得下面的定理:

定理3.2 设G(a,4,b)(a≥1,b≥1)是a+4+b个点的图,则它的Hosoya指标排序为

(1)当a+b=4k时

(2)当a+b=4k+1时

(3)当a+b=4k+2时

(4)当a+b=4k+3时

猜你喜欢
心形能级结论
由一个简单结论联想到的数论题
立体几何中的一个有用结论
Heart心形浪漫
提升医学教育能级 培养拔尖创新人才
纠缠Ξ-型三能级原子与纠缠腔场相互作用熵的纠缠演化
心形贺卡
制作心形贺卡
光谱、能级和能级图的理解和应用
结论
中医医院能级护士培训及能级划分的探讨