吴量,刘小花,汪一航
(1.宁波大学理学院,浙江 宁波 315211;2.青海民族大学数学与统计学院,青海 西宁 810007)
本文仅考虑有限无向的简单图.设一个图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.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.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时3 主要定理及证明