本文中仅考虑有限无向的简单图. 设G是有n个点的图,G的一个匹配是指G的一个生成子图, 它的每个分支是孤立点或孤立边. 恰有k条边的匹配称为k-匹配. 在文献[1] 中图G的匹配多项式定义为:μ(G,x)=∑_k≥0(-1)^km(G,k)xⁿ-2k,这里m(G,k)是G中的k-匹配的数目. 为了方便,本文中有时将μ(G,x)简记为μ(G).

图的匹配多项式在数学、统计物理和化学中都有很重要的应用. 在统计物理中,图的匹配多项式是描述一种物理系统的数学模型. 事实上,为了研究这种物理系统,物理学家Heilmann等^[2]引进了图的二元匹配多项式, 如果令其中的一个变量为常数,便得到本文中所研究的一元匹配多项式. 在理论化学中,图的匹配多项式的所有系数绝对值之和(即所有的匹配总数)就是这个图所表示的碳氢化合物的Hosoya指标^[3],记为Z(G)=∑_k≥0m(G,k), 该指标与相应的碳氢化合物的沸点有关. 而图的匹配多项式的所有根的绝对值之和定义为图的匹配能量,它与该图所表示的芳香烃的活性有关^[4].

定义1 设λ₁,λ₂,…,λ_n是图G的匹配多项式的所有根,定义它的匹配能量为ME(G)=∑ⁿ_i=1|λ_i|.

图的匹配能量衍生自图的能量,即图的特征多项式的所有根的绝对值之和. 在Hückel分子轨道理论中,共轭碳氢化合物的分子图的π-电子能量水平近似地等于该分子图的能量. 对图的能量目前已有了大量的研究,见文献[5]. 由于无圈图的特征多项式等于匹配多项式^[1],故在无圈图上,能量和匹配能量是一致的. 自从2012年 Gutman等^[4]提出图的匹配能量的概念以来,对这个主题已经有了大量的研究,Gutman等^[4]指出在所有n阶图中,匹配能量最小的是空图,最大的是完全图, 也确定了匹配能量最小和最大的连通单圈图.Gutman等^[6-7]确定了匹配能量最大和最小的连通双圈图.Ji等^[8]、Chen等^[9]确定了匹配能量最大和最小的连通三圈图.Li等^[10]确定了所有κ-连通图中的匹配能量最大的图和所有χ-色图中匹配能量最大的图等. 纵观这些研究结果,主要都集中在对给定的一类图刻画其匹配能量达到极值的图, 但很少有文献对一类图的匹配能量给一个完全的排序,在这篇文章中,本研究对一类所谓的θ(a,b,c)-图做这样的工作,虽然不能给出3个变量(a,b,c)下的完全排序,但当其中的一个变量固定时,能给出顶点数相同的θ -图之间匹配能量的一个完全排序,同时也给出了这些图的Hosoya指标的一个完全排序.

设G是一个图,以V(G),E(G)分别表示图G的点集和边集.如果e∈E(G), 以G\e表示从图G中删去边e后得到的图. 如果V₁?V(G),以G\V₁表示从图G中删去V₁中的所有点以及和这些点关联的所有边后得到的图. 如果V₁={u},将G\{u}简记为G\u.以G∪H表示两个图G和H的并图. 以P_n、C_n、K_n分别表示n个点的路、圈和完全图. 本研究把3条路P_a+2,P_b+2和P_c+2的两个端点分别黏结成为两个点后得到的图称为θ(a,b,c)图(见图1). 为了方便,本研究把3条路P_a+1、P_b+1和P_c+1的一个端点黏结成为一个点后得到的图称为T(a,b,c)图,把图P_a∪P_b∪…∪P_c简记为P(a,b,…,c).

图1 图θ(a,b,c)(0≤a≤b≤c)
Fig.1 Fig θ(a,b,c)(0≤a≤b≤c)

引理1^[1] 设图G有k个连通分支G₁,G₂,…,G_k,则μ(G,x)=μ(G₁,x)μ(G₂,x)…μ(G_k,x).

引理2^[1]设G是一个图,u∈V(G),e=uv∈E(G),则(i)μ(G,x)=xμ(G\u,x)-∑_i～uμ(G\{u,i},x),(ii)μ(G,x)=μ(G\e,x)-μ(G\{u,v},x).

引理3 设P_s+t是s+t个点的路,s≥2,t≥2,P(s,t)=P_s∪P_t,则μ(P_s+t)=μ(P(s,t))-μ(P(s-1,t-1)).

证明 由引理2的(ii),显然.注记 假如本研究约定μ(P₀)=1,μ(P_1)=0,引理3对s≥0也是对的.下面的引理4在后面的计算中扮演重要的角色.

引理4 设P(s,t)=P_s∪P_t,0≤k≤s≤t,则μ(P(s,t))-μ(P(s-k,t+k))=μ(P(k-1,t- s+k-1)).

证明 由引理3,μ(P_s+t)=μ(P(s,t))-μ(P(s-1,t-1)),μ(P_s+t)=μ(P(s-k,t+k))-μ(P(s-k-1,t+k-1)),两式相减得μ(P(s,t))-μ(P(s-k,t+k))=μ(P(s-1,t- 1))-μ(P(s-k-1,t+k-1)).重复应用上式得μ(P(s,t))-μ(P(s-k,t+k))=μ(P(s-(s-k),t-(s-k)))-μ(P(s-k-(s-k),t+k-(s-k)))=μ(P(k,t-s+k))-μ(P(0,t-s+2k))=μ(P(k-1,t-s+k-1)).

引理5^[4] 设G是一个图,则ME(G)=2/(π)∫⁺∞₀1/(x²)ln[∑_k≥0m(G,k)x²k]dx,这里m(G,k)是G中的k-匹配的数目.由引理5,本研究规定一种偏序关系“≤”.设G₁、G₂是两个n阶图,对所有的非负整数k,若满足m(G₁,k)≤m(G₂,k),则定义G₁G₂. 如果不等式m(G₁,k)≤m(G₂,k)对某个非负整数k是严格的,则定义G₁?G₂. 于是,由引理5,可以得到下面的结果:

引理6 设G₁,G₂是两个n阶图,如果存在一个m阶图H和正整数t,使得μ(G₁)-μ(G₂)=tμ(H),则

(i)n-m是一个偶数.

(ii)如果n-m≡0(mod4),则G₁G₂.

(iii)如果n-m≡2(mod4),则G₁?G₂.

证明(i)由于多项式μ(G_i,x)(i=1,2)中xⁿ-(2k-1)的系数均为零,则多项式μ(G₁,x)-μ(G₂,x)中x^n-(2k-1)的系数也为零.于是,对某个整数k,tμ(H)的首项tx^m必定是形如tx^n-2k.故n-2k=m. 则n-m是一个偶数.

(ii)不妨设n=m+4k,μ(G₁)=xⁿ-m(G₁,1)x^n-2+…+m(G₁,2k)x^m-m(G₁,2k+1)x^m-2+…,μ(G₂)=xⁿ-m(G₂,1)x^n-2+…+m(G₂,2k)x^m-m(G₂,2k+1)x^m-2+…,μ(H)=x^m-m(H,1)x^m-2+….由于μ(G₁)=μ(G₂)+tμ(H),比较系数得,m(G₁,s)={m(G₂,s), s<2k,m(G₂,s)+t m(H,s-2k), s≥2k,所以G₁G₂.

(iii)不妨设n=m+4k+2,μ(G₁)=xⁿ-m(G₁,1)xⁿ-2+…-m(G₁,2k+1)x^m+m(G₁,2k+2)x^m-2-…,μG₂)=xⁿ-m(G₂,1)xⁿ-2+…-m(G₂,2k+1)x^m+m(G₂,2k+2)x^m-2-…,μ(H)=x^m-m(H,1)x^m-2+….由于μ(G₁)=μ(G₂)+tμ(H),比较系数得,m(G₁,s)={m(G₂,s), s<2k+1,m(G₂,s)-t m(H,s-2k-1), s≥2k+1,所以G₁?G₂.

为了方便,下面本研究约定P₀、P_1、P_2都是空图,且μ(P₀)=1,μ(P_1)=0,μ(P_2)=-1.T(0,b,c)=P_b+c+1,T(-1,b,c)=P(b,c).如a=2时,μ(P(a-2,b,c))=μ(P₀)μ(P_b)μ(P_c)=μ(P(b,c)),μ(P(a-3,b,c))=μ(P_1)μ(P_b)μ(P_c)=0,μ(P(a-4,b,c))=μ(P_2)μ(P_b)μ(P_c)=-μ(P_b)μ(P_c).

引理7 设1≤a≤b,0≤c,则μ(T(a,b,c))-μ(T(a-2,b+2,c))=-μ(P(1, b-a+1,c-1)).证明 当c=0,时,T(a,b,0)=T(a-2,b+2,0)=P(a+b+1),μ(P_1)=0,结论显然成立.当c≥1时,(i)当a=1时,μ(T(a,b,c))=xμ(P(1,b,c))-μ(P(b,c))-μ(P(1,b-1,c))-μ(P(1,b,c-1)),μ(T(a-2,b+2,c))=μ(P(b+2,c))=xμ(P(b+1,c))-μ(P(b,c)),μ(T(a,b,c))-μ(T(a-2,b+2,c))=x[μ(P(1,b,c))-μ(P(b+1,c))]-μ(P(1,b-1,c))-μ(P(1,b,c-1))=xμ(P(0,b-1,c))-μ(P(1,b-1,c))-μ(P(1,b,c-1))=-μ(P(1,b,c-1))=-μ(P(1,b-a+1,c-1)).结论成立.(ii)当a≥2时,μ(T(a,b,c))=xμ(P(a,b,c))-μ(P(a-1, b,c))-μ(P(a,b-1,c))-μ(P(a,b,c-1)),μ(T(a-2,b+2,c))=xμ(P(a-2,b+2,c))-μ(P(a-3,b+2,c))-μ(P(a-2,b+1,c))-μ(P(a-2,b+2,c-1)),由引理4,μ(T(a,b,c))-μ(T(a-2,b+2,c))=x[μ(P(a,b,c))-μ(P(a-2,b+2,c))]-[μ(P(a-1,b,c))-μ(P(a-3,b+2,c))]-[μ(P(a,b-1,c))-μ(P(a-2,b+1,c))]-[μ(P(a,b,c-1))-μ(P(a-2,b+2,c-1))]=xμ(P(1,b-a+1,c))-μ(P(1,b-a+2,c))-μ(P(1,b-a,c))-μ(P(1,b-a+1,c-1))=-μ(P(1,b-a+1,c-1)).注意,在上述第2个方括号中,当a=2时,μ(P(a-1,b,c))=μ(P(1,b,c)),μ(P(a-3,b+2,c))=0, 结论也成立.

引理8 设c≥0,k≥1,(i)μ(T(2k-1,2k+1,c))-μ(T(2k,2k,c))=μ(P_c-1).(ii)μ(T(2k-2,2k+1,c))-μ(T(2k-1,2k,c))=μ(P(1,c-1)).证明(i)当c=0时,T(2k-1,2k+1,0)=P₄k+1=T(2k,2k,0),μ(P_1)=0,结论显然成立.当c≥1时,μ(T(2k-1,2k+1,c))=xμ(P(2k-1,2k+1,c))-μ(P(2k-2,2k+1,c))-μ(P(2k-1,2k,c))-μ(P(2k-1,2k+1,c-1)),μ(T(2k,2k,c))=xμ(P(2k,2k,c))-μ(P(2k-1,2k,c))-μ(P(2k,2k-1,c))-μ(P(2k,2k,c-1)),则μ(T(2k-1,2k+1,c))-μ(T(2k,2k,c))=x[μ(P(2k-1,2k+1,c))-μ(P(2k,2k,c))]-[μ(P(2k-2,2k+1,c))-μ(P(2k,2k-1,c))]-[μ(P(2k-1,2k+1,c-1))-μ(P(2k,2k,c-1))]=x(-μ(P(0,0,c))-(-μ(P(0,1,c))-(-μ(P(0,0,c-1))=μ(P(0,0,c-1))=μ(P_c-1).(ii)证明与(i)类似,略.

引理9 设c≥0,k≥0,(i)μ(T(2k+1,2k+1,c))-μ(T(2k,2k+2,c))=-μ(P_c-1).(ii)μ(T(2k,2k+1,c))-μ(T(2k-1,2k+2,c))=-μ(P(1,c-1)).证明(i)当c=0时,T(2k+1,2k+1,0)=P₄k+3=T(2k,2k+2,0),μ(P_1)=0,结论显然成立.当c≥1时,μ(T(2k+1,2k+1,c))=xμ(P(2k+1,2k+1,c))-μ(P(2k,2k+1,c))-μ(P(2k+1,2k,c))-μ(P(2k+1,2k+1,c-1)),μ(T(2k,2k+2,c))=xμ(P(2k,2k+2,c))-μ(P(2k-1,2k+2,c))-μ(P(2k,2k+1,c))-μ(P(2k,2k+2,c-1)),则μ(T(2k+1,2k+1,c))-μ(T(2k,2k+2,c))=x[μ(P(2k+1,2k+1,c))-μ(P(2k,2k+2,c))]-[μ(P(2k+1,2k,c))-μ(P(2k-1,2k+2,c))]-[μ(P(2k+1,2k+1,c-1))-μ(P(2k,2k+2,c-1))]=x(μ(P(0,0,c))-(μ(P(0,1,c))-(μ(P(0,0,c-1))=-μ(P(0,0,c-1))=-μ(P_c-1).(ii)证明与(i)类似,略.

引理10 设2≤a≤b,0≤c,则μ(θ(a,b,c))-μ(θ(a-2,b+2,c))=μ(P(1,b- a+1,c-2)).证明 当c=0时,μ(θ(a,b,0))=xμ(T(a,b,0))-μ(T(a-1,b,0))-μ(T(a,b-1,0))-μ(P(a,b)),μ(θ(a-2,b+2,0))=xμ(T(a-2,b+2,0))-μ(T(a-3,b+2,0))-μ(T(a-2,b+1,0))-μ(P(a-2,b+2)).由于T(a,b,0)=P_a+b+1=T(a-2,b+2,0),则μ(θ(a,b,c))-μ(θ(a-2,b+2,c))=μ(P(a-2,b+2))-μ(P(a,b))=-μ(P(1,b-a+1)),再由约定μ(P_2)=-1知,结论成立.当c=1时,μ(θ(a,b,1))=xμ(T(a,b,1))-μ(T(a-1,b,1))-μ(T(a,b-1,1))-μ(T(a,b,0)),μ(θ(a-2,b+2,1))=xμ(T(a-2,b+2,1))-μ(T(a-3,b+2,1))-μ(T(a-2,b+1,1))-μ(T(a-2,b+2,0)).由引理7知,μ(θ(a,b,1))-μ(θ(a-2,b+2,1))=-xμ(P(1,b-a+1,0))+μ(P(1,b-a+2,0))+μ(P(1,b-a,0))=0=μ(P(1,b-a+1,-1)).当c≥2时,μ(θ(a,b,c))=xμ(T(a,b,c))-μ(T(a-1,b,c))-μ(T(a,b-1,c))-μ(T(a,b,c-1)),μ(θ(a-2,b+2,c))=xμ(T(a-2,b+2,c))-μ(T(a-3,b+2,c))-μ(T(a-2,b+1,c))-μ(T(a-2,b+2,c-1)).由引理7知,μ(θ(a,b,c))-μ(θ(a-2,b+2,c))=-xμ(P(1,b-a+1,c-1))+μ(P(1,b-a+2,c-1))+μ(P(1,b-a,c-1))+μ(P(1,b-a+1,c-2))=μ(P(1,b-a+1,c-2)).

引理11 设c≥0,k≥1,则μ(θ(2k-1,2k+1,c))-μ(θ(2k,2k,c))=-μ(P_c-2).证明 当c=0时,μ(θ(2k-1,2k+1,0))=xμ(T(2k-1,2k+1,0))-μ(T(2k-2,2k+1,0))-μ(T(2k-1,2k,0))-μ(P(2k-1,2k+1)),μ(θ(2k-1,2k+1,0))-μ(θ(2k,2k,0))=-[μ(P(2k-1,2k+1))-μ(P(2k,2k))]=μ(P(0,0))=1=-μ(P(c-2)).结论成立.当c≥1时,μ(θ(2k-1,2k+1,c))=xμ(T(2k-1,2k+1,c))-μ(T(2k-2,2k+1,c))-μ(T(2k-1,2k,c))-μ(T(2k-1,2k+1,c-1)).由引理8,μ(θ(2k-1,2k+1,c))-μ(θ(2k,2k,c))=x[μ(T(2k-1,2k+1,c))-μ(T(2k,2k,c))]-[μ(T(2k-2,2k+1,c))-μ(T(2k-1,2k,c))]-[μ(T(2k-1,2k+1,c-1))-μ(T(2k,2k,c-1))]=xμ(P(c-1))-μ(P(1,c-1))-μ(P(c-2))=-μ(P(c-2)).

引理12设c≥0,k≥1,则μ(θ(2k+1,2k+1,c))-μ(θ(2k,2k+2,c))= μ(P_c-2).证明 当c=0时,μ(θ(2k+1,2k+1,0))=xμ(T(2k+1,2k+1,0))-μ(T(2k,2k+1,0))-μ(T(2k+1,2k,0))-μ(P(2k+1,2k+1)).μ(θ(2k+1,2k+1,0))-μ(θ(2k,2k+2,0))=-[μ(P(2k+1,2k+1))-μ(P(2k,2k+2))]=-μ(P(0,0))=-1=μ(P(c-2)).当c≥1时,μ(θ(2k+1,2k+1,c))=xμ(T(2k+1,2k+1,c))-μ(T(2k,2k+1,c))-μ(T(2k+1,2k,c))-μ(T(2k+1,2k+1,c-1)).由引理9,μ(θ(2k+1,2k+1,c))-μ(θ(2k,2k+2,c))=x[μ(T(2k+1,2k+1,c))-μ(T(2k,2k+2,c))]-[μ(T(2k,2k+1,c))-μ(T(2k-1,2k+2,c))]-[μ(T(2k+1,2k+1,c-1))-μ(T(2k,2k+2,c-1))]=-xμ(P(c-1))+μ(P(1,c-1))+μ(P(c-2))=μ(P(c-2)).定理1 设c≥0是一个固定整数,则(i)当a+b=4k,θ(1,4k-1,c)?θ(3,4k-3,c)?θ(5,4k-5,c)?…?θ(2k-1,2k+1,c)?θ(2k,2k,c)?θ(2k-2,2k+2,c)?…?θ(4,4k-4,c)?θ(2,4k-2,c)?θ(0,4k,c);(ii)当a+b=4k+1,θ(1,4k,c)?θ(3,4k-2,c)?θ(5,4k-4,c)?…?θ(2k+1,2k,c)=θ(2k,2k+1,c)?θ(2k-2,2k+3,c)?…?θ(4,4k-3,c)?θ(2,4k-1,c)?θ(0,4k+1,c);(iii)当a+b=4k+2,θ(1,4k+1,c)?θ(3,4k-1,c)?θ(5,4k-3,c)?…?θ(2k+1,2k+1,c)?θ(2k,2k+2,c)?θ(2k-2,2k+4,c)?…?θ(4,4k-2,c)?θ(2,4k,c)?θ(0,4k+2,c);(iv)当a+b=4k+3,θ(1,4k+2,c)?θ(3,4k,c)?θ(5,4k-2,c)?…?θ(2k+3,2k,c)=θ(2k,2k+3,c)?θ(2k-2,2k+5,c)?…?θ(4,4k-1,c)?θ(2,4k+1,c)?θ(0,4k+3,c).证明 由引理10知,当2≤a≤b,0≤c时,有μ(θ(a,b,c))-μ(θ(a-2,b+2,c))=μ(P(1,b- a+1,c-2)).(1)等式(1)左端的图的点数为a+b+c+2, 右端的图的点数为b+c-a,它们的差为2a+2.于是由引理6知,当a为奇数时有θ(a,b,c)θ(a-2,b+2,c), 当a为偶数时有θ(a,b,c)?θ(a-2,b+2,c), 由此便得到(i)～(iv)中的不等式的前半段和后半段.由引理11知,当c≥0,k≥1时,有μ(θ(2k-1,2k+1,c))-μ(θ(2k,2k,c))= -μ(P_c-2).(2)式(2)左端的图的点数为4k+c+2, 右端的图的点数为c-2,它们的差为4k+4.于是由引理6,得到定理中(i)的中间的不等式θ(2k-1,2k+1,c)?θ(2k,2k,c).由引理12知,当c≥0,k≥1时,有μ(θ(2k+1,2k+1,c))-μ(θ(2k,2k+2,c))= μ(P_c-2).(3)式(3)左端的图的点数为4k+c+4, 右端的图的点数为c-2,它们的差为4k+6.于是由引理6,得到定理中(iii)的中间的不等式θ(2k+1,2k+1,c)?θ(2k,2k+2,c).定理证毕.

下面的推论1和推论2是定理1的直接推论.

推论1 设c≥0是一个固定整数,则θ(a,b,c)图的匹配能量大小排序规律如下:

(i)当a+b=4k,ME(θ(1,4k-1,c))

(ii)当a+b=4k+1,ME(θ(1,4k,c))

(iii)当a+b=4k+2,ME(θ(1,4k+1,c))

(iv)当a+b=4k+3,ME(θ(1,4k+2,c))

推论2 设c≥0是一个固定整数,则θ(a,b,c)图的Hosoya指标的大小排序规律如下:

(i)当a+b=4k,Z(θ(1,4k-1,c))

(ii)当a+b=4k+1,Z(θ(1,4k,c))

(iii)当a+b=4k+2,Z(θ(1,4k+1,c))

(iv)当a+b=4k+3,Z(θ(1,4k+2,c))

推论3(i)在n个点的θ -图中,匹配能量第一小、第二小和第三小的图分别为θ(1,1,n-4),θ(1,3,n-6)和θ(1,5,n-8).

(ii)在n个点的θ -图中,匹配能量第一大和第二大的图分别为θ(0,2,n-4)和θ(0,4,n-6).

证明(i)观察推论1(i)～(iv), 匹配能量达到最小的图中必有一个参数为1,固定c=1,在此类图中,匹配能量前三小的图是θ(1,1,n-4),θ(1,3,n-6),θ(1,5,n-8).除至少有一个参数是1的所有图外,匹配能量达到最小的图至少有一个参数是3,此类图中匹配能量最小的图是θ(3,3,n-8).然而ME(θ(1,5,n-8))

(ii)观察推论1(i)～(iv), 匹配能量达到最大的图中必有一个参数为0, 固定c=0, 在此类图中,匹配能量前两大的图是θ(0,2,n-4),θ(0,4,n-6),除至少有一个参数是0的所有图外,匹配能量达到最大的图至少有一个参数是2, 此类图中匹配能量最大的图是θ(2,2,n-6).然而ME(θ(0,4,n-6))>ME(θ(2,2,n-2)).于是在n个点的θ -图中,匹配能量第一大和第二大的图分别为θ(0,2,n-4)和θ(0,4,n-6).

推论4(i)在n个点的θ -图中,Hosoya指标第一小、第二小和第三小的图分别为θ(1,1,n-4),θ(1,3,n-6)和θ(1,5,n-8).

(ii)在n个点的θ -图中,Hosoya指标第一大和第二大的图分别为θ(0,2,n-4)和θ(0,4,n-6).证明 证明与推论3类似,略.