图2-2nP5和2-nK1,1,1,3完美匹配的计数

唐保祥, 任 韩

(1. 天水师范学院 数学与统计学院, 甘肃 天水 741001； 2. 华东师范大学 数学系, 上海 200062)

1 引言与预备知识

对于图完美匹配的计数, 目前已有一些精巧的计数方法[1-4], 但还没有一般的方法求一般图完美匹配的数目. 文献[5-8]研究表明, 对于一些特殊图, 把所研究的图按照匹配某个顶点的完美匹配分类, 先求出每一类完美匹配数目的递推关系式, 即可得所研究图的完美匹配数目计数公式.

定义1如果图G有一个1-正则生成子图, 则称该生成子图为图G的完美匹配.

定义2设S1,S2是图G的两个完美匹配, 如果S1和S2中有一条边不同, 则称S1和S2是图G两个不同的完美匹配.

图1 图2-2nP5

图2 图2-nK1,1,1,3

2 主要结果

定理1令η(2n)是图2-2nP5的完美匹配数, 则

(1)

证明: 图2-2nP5显然存在完美匹配. 要求函数η(2n)的解析式, 先要定义图G1并求出其完美匹配数的递推式. 把路pq的端点p,q分别与图2-2nP5的顶点u11,u13连接一条边产生的图记为G1, 如图3所示. 由图3可见, 图G1存在完美匹配, 用μ(2n)表示图G1的完美匹配数. 设图G1完美匹配的集合为P, 图G1含有边pq,pu11的完美匹配集合分别为P1,P2, 则P1∩P2=Ø,P=P1∪P2, 故μ(2n)=|P|=|P1|+|P2|. 因为pq∈P1, 所以pu11,qu13∉P1, 故由η(2n)的定义知, |P1|=η(2n).

图3 图G1

μ(2n)=η(2n)+η(2(n-1))+μ(2(n-1)).

(2)

|S3|=4η(2(n-1))+μ(2(n-1)).

综上, 有

η(2n)=11η(2(n-1))+2μ(2(n-1)).

(3)

由式(2)得

μ(2(n-1))=η(2(n-1))+η(2(n-2))+μ(2(n-2)),

(4)

把式(4)代入式(3), 得

η(2n)=13η(2(n-1))+2η(2(n-2))+2μ(2(n-2)).

(5)

由式(3)得

η(2(n-1))=11η(2(n-2))+2μ(2(n-2)),

(6)

将式(5),(6)消去μ(2(n-2)), 得

η(2n)=14η(2(n-1))-9η(2(n-2)).

(7)

其中c1,c2为待定常数. 图4为图2-2×1P5的完美匹配. 由图4知,η(2×1)=13,μ(2×1)=15. 从而由式(3)得η(2×2)=173. 故式(1)成立.

图4 图2-2×1P5的完美匹配

定理2令λ(n)为图2-nK1,1,1,3的完美匹配数, 则

(8)

证明: 图2-nK1,1,1,3显然存在完美匹配. 要求函数λ(n)的解析式, 先要定义图G2并求出其完美匹配数的递推式. 把路wt的端点w,t分别与图2-nK1,1,1,3的顶点u11,v11连接一条边生成的图记为G2, 如图5所示. 由图5可见, 图G2有完美匹配, 用π(n)表示图G2的完美匹配数. 设图G2完美匹配的集合为S, 图G2含有边wt,wu11的完美匹配集合分别为S1,S2, 则S1∩S2=Ø,S=S1∪S2, 从而π(n)=|S|=|S1|+|S2|. 因为wt∈S1, 所以wu11,tv11∉S1, 故由λ(n)的定义知, |S1|=λ(n).

图5 图G2

π(n)=λ(n)+λ(n-1)+π(n-1).

(9)

λ(n)=4λ(n-1)+2π(n-1).

(10)

由式(9)得

π(n-1)=λ(n-1)+λ(n-2)+π(n-2),

(11)

把式(11)代入式(10), 得

λ(n)=6λ(n-1)+2λ(n-2)+2π(n-2).

(12)

由式(10), 得

λ(n-1)=4λ(n-2)+2λ(n-2),

(13)

将式(12),(13)消去π(n-2), 得

λ(n)=7λ(n-1)-2λ(n-2).

(14)

其中c1,c2为待定常数. 图6为图2-1K1,1,1,3的完美匹配. 由图6知,λ(1)=6. 图7为图G3的完美匹配, 由图7知,π(1)=8. 从而由式(10)得λ(2)=40. 故式(8)成立.

图6 图2-1K1,1,1,3的完美匹配

图7 图G3的完美匹配