一类柱面与Möbius带的匹配多项式①

马海成， 攸晓杰

青海民族大学 数学与统计学院，西宁 810007

本文仅考虑有限无向的简单图． 设G是有n个点的图． 若G的一个生成子图的每个分支是一个孤立点或者一条边, 则称此生成子图为G的一个匹配． 恰有k条边的匹配称为k-匹配． 饱和了G的所有顶点的匹配称为G的完美匹配, 图G的完美匹配的个数记为pm(G)． 文献[1]定义了图G的匹配多项式为

(1)

这里W=(x,y),x和y分别是点和边的权重,p(G,k)是G的所有k-匹配的数目, 且约定p(G, 0)=1． 假如令y=-1, 我们便得到文献[2]中定义的匹配多项式

(2)

(1),(2)式互相确定, 本文使用(2)式为图G的匹配多项式, 并将μ(G,x)简记为μ(G)． 匹配多项式在数学、 统计物理和化学中都有很重要的应用． 在统计物理领域, 匹配多项式是描述一种物理系统的数学模型, 首先由文献[3]引入． 在理论化学领域, 匹配多项式的根的绝对值之和称为该图的匹配能量, 与这个图所表示的芳香烃的活性有关[4]． 匹配多项式的所有系数的绝对值之和(即所有匹配的总数)就是这个图表示的碳氢化合物的Hosoya指标, 与这个化合物的沸点有关[5]． 匹配多项式是一种组合计数多项式, 它与图的特征多项式、 色多项式和其他多项式有许多联系[6-9]． 对于给定的图, 计算这个图的匹配多项式是一个困难的问题, 文献[10-13]计算了许多图的匹配多项式． 关于Hosoya指标的研究可参见文献[14], 关于匹配多项式对图的刻画的研究可参见文献[15-19]． 截至目前, 还有许多基本图的匹配多项式仍然未知, 如本文所涉及的柱面和Möbius带, 这是两个较为基本的图, 但其匹配多项式未知． 作为对匹配多项式研究的补充, 本文给出了这两个图的匹配多项式, 并计算了这些图上的完美匹配的个数．

设G=(V(G),E(G))是一个简单图,V(G)是其顶点集,E(G)是其边集, 其中E(G)的每一个元素是V(G)上的无序对, 称为一条边． 如果e∈E(G), 以Ge表示从图G中删除边e后得到的图． 如果v∈V(G), 以Gv表示删去点v以及与之相关联的所有边后得到的图． 以Pn,Cn分别表示n个点的路、 圈． 给两条n个点的路, 其顶点从左向右分别标记为1,2,…,n和1′,2′,…,n′, 将这两条路上的点i和i′(i=1,2,…,r)分别用一条边连接, 得到的图记为Ln,r(见图1)． 把Ln,n称为梯子, 简记为Ln． 将图Ln,r的顶点1和n, 1′和n′分别用一条边连接得到的图记为Zn,r,Zn,n称为柱面, 简记为Zn． 将图Ln,r的顶点1和n′, 1′和n分别用一条边连接得到的图记为Mn,r,Mn,n称为Möbius带, 记为Mn(见图2)． 从梯子Ln中删去点n后得到的图记为Sn(见图3)． 设G和H是两个点不交的图, 定义图G和H的乘积图为G×H, 其顶点集为V(G)×V(H), 两个点(u1,v1),(u2,v2)∈V(G×H)在图G×H中邻接当且仅当u1=u2,v1与v2在图H中邻接, 或u1与u2在G中邻接,v1=v2． 于是, 梯子Ln,n=Pn×P2, 柱面图Zn,n=Cn×P2．

图1 图Ln,r

图2 图Zn,n和Mn,n

图3 图Sn

1 柱面和Möbius带的匹配多项式

引理1[9]设图G有k个连通分支:G1,G2,…,Gk, 则

μ(G,x)=μ(G1,x)μ(G2,x)…μ(Gk,x)

引理2[9]设G是一个图,u∈V(G),e=uv∈E(G), 则:

(ii)μ(G,x)=μ(Ge,x)-μ(G{u,v},x)．

引理3[9]

引理4[14]设G是有n个点的图, 则

其中i是复数单位,i2=-1．

定理1

证对Ln的边e=(n-1,n)、Sn的边e′=((n-1)′,n′)使用引理2, 便得到(3)式的前两个式子． 为了使(3)式的系数矩阵是一个方阵, 我们填上第3个式子．

(3)

令(3)式的系数矩阵为

设矩阵A的特征多项式为

f(λ)=λ3-d1λ2+d2λ-d3

(4)

其中d1=μ(P2)-1=x2-2,d2=-μ(P2)+2μ(P1)2-1=x2,d3=1．

μ(Ln)满足递推关系式

μ(Ln)=d1μ(Ln-1)-d2μ(Ln-2)+d3μ(Ln-3)

(5)

初始条件为

μ(L0)=1μ(L1)=μ(P2)=x2-1μ(L2)=μ(C4)=x4-4x2+2

(6)

因为(5)式的变量为t的生成函数

且

由生成函数的定义, 定理 1得证．

定理2

其中μ(L0,0)=1．

证对Ln,r的边er=(r,r′),er-1=(r-1, (r-1)′),…,e1=(1, 1′)依次使用引理2(ii), 便得到下列式子:

μ(Ln,r)=μ(Ln,r-1)-μ(Lr-1,r-1)(μ(Pn-r))2

μ(Ln,r-1)=μ(Ln,r-2)-μ(Lr-2,r-2)(μ(Pn-r+1))2

…

μ(Ln,1)=μ(P2n)=(μ(Pn))2-(μ(Pn-1))2

将以上各式相加, 得到

定理3

其中Ln-1,0=2Pn-1．

证对Zn,n的边en=(n,n′),en-1=(n-1, (n-1)′),…,e1=(1, 1′) 依次使用引理2(ii), 便得到下列式子:

μ(Zn,n)=μ(Zn,n-1)-μ(Ln-1,n-1)

μ(Zn,n-1)=μ(Zn,n-2)-μ(Ln-1,n-2)

…

μ(Zn,1)=μ(Cn)2-μ(Pn-1)2

相加上面各式, 定理 3得证．

定理4

其中Ln-1,0=2Pn-1．

证对Mn,n的边en=(n,n′),en-1=(n-1, (n-1)′),…,e1=(1, 1′)依次使用引理2(ii), 便得到下列式子:

μ(Mn,n)=μ(Mn,n-1)-μ(Ln-1,n-1)

μ(Mn,n-1)=μ(Mn,n-2)-μ(Ln-1,n-2)

…

μ(Mn,1)=μ(C2n)-μ(Pn-1)2

相加上面各式, 定理 4得证．

推论1(i)μ(Mn,n)-μ(Zn,n)=μ(C2n)-μ(Cn)2;

(ii)

(iii)Z(Mn,n)-Z(Zn,n)=Z(C2n)-Z(Cn)2．

证由定理3和定理4, (i)显然．

(ii)由匹配多项式的定义知

由(i)和引理3知

当n为奇数时, (-1)n(μ(C2n, 0)-μ(Cn, 0)2)=(-1)n((-1)n×2-0)=2．

(iii)由引理4和(i)知

推论1得证．

2 梯子、 柱面和Möbius带的完美匹配数

推论2

证在定理1中令k2=0,x=0, 便得该表达式的常数项为

由于Ln的完美匹配数pm(Ln)等于多项式μ(Ln,x)的常数项乘(-1)n, 于是

注1很容易计算Ln的完美匹配数就是著名的斐波那契数, 其前几项的值L1,L2,L3,L4的完美匹配数分别为1,2,3,5, 与推论2计算的值是吻合的． 推论2给出了斐波那契数的另外一种表示法．

推论3(i) 当n为偶数时,

(ii) 当n为奇数时,

证众所周知, 当n=4m或n=4m+2时, 路Pn的匹配多项式的常数项为1或-1; 当n为奇数时, 路Pn的匹配多项式的常数项均为0． 令x=0, 便得:

当n为偶数时, 定理2中表达式的常数项为

于是

当n为奇数时, 定理 2中表达式的常数项为

推论4(i) 当n为偶数时,

(ii) 当n为奇数时,

证众所周知, 当n=4m或n=4m+2时, 圈Cn的匹配多项式的常数项为2或-2; 当n为奇数时, 圈Cn的匹配多项式的常数项均为0, 令x=0, 便得:

当n为偶数时, 由推论3知, 定理3中表达式的常数项为

当n为奇数时, 定理3中表达式的常数项为

注2容易验证图Z3和Z4的完美匹配数分别为4和9, 与推论4计算的值是吻合的．

推论5(i) 当n为偶数时,

(ii) 当n为奇数时,

证令x=0, 便得:

当n为偶数时, 由推论3知, 定理4中表达式的常数项为

当n为奇数时, 定理4中表达式的常数项为

注3容易验证图M3和M4的完美匹配数分别为6和7, 与推论5计算的值是吻合的．