2类特殊图的完美对集数的分类递推求法

唐保祥,任 韩

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

图的完美对集计数理论是近30年来图论研究的热点问题之一[1-6]. 对于存在完美对集的图,把完美对集按照关联某个顶点的边进行分类,求出每一类完美匹配数目的递推关系式,再把各类完美对集的递推式相加,就得到一组有相互联系的递推关系式,利用这些递推式之间的相互关系,消去那些不需要的递推关系式,从而得到这个图的完美对集数目的递推关系式,最后求出这个递推式的通解,进而就得到这个图的完美对集数目的显式公式[7-14]. 这个方法为图的完美对集理论的应用提供了支持.

1 基本概念

定义1若图G有一个1-正则生成子图,则称这个生成子图为图G的完美对集.

定义2设图G是一个有完美对集的图,若图G的两个完美对集W1和W2中有一条边不同,则称W1和W2是G的两个不同的完美对集.

图1 图2-nP8Fig.1 Figure of 2-nP8

图2 图2-nZ3Fig.2 Figure of 2-nZ3

2 主要结果

定理1设图2-nP8的完美对集数为f(n),则

证明容易看出图2-nP8有完美对集. 为了计算f(n)的表达式,先定义一个图G1. 把路xy的端点x,y分别与图2-nP8的顶点u16,u15连接一条边得到的图记为G1,如图3所示.

图3 图G1Fig.3 Figure of G1

容易看出图G1有完美对集. 设图G1的完美对集数为g(n),图G1的完美对集集合为W,按照W中元素饱和顶点x的情况可分两类:设W中包含边xy的完美对集集合为W1,W中包含边xu16的完美对集集合为W2,根据不同完美对集的定义知,W1∩W2=φ,W=W1∪W2,故g(n)=|W|=|W1|+|W2|.

因为xy∈W1,故xu16,yu15∉W1,由f(n)的定义知,|W1|=f(n).

故

g(n)=f(n)+3f(n-1)+2g(n-1).

(1)

再求f(n)的递推式. 设图2-nP8的完美对集集合为W,图2-nP8包含边u16u11,u16v11,u16u15的完美对集集合分别为W1,W2,W3,则Wi∩Wj=φ(1≤i

综上所述,

f(n)=5f(n-1)+5g(n-1).

(2)

由式(1),得

g(n-1)=f(n-1)+3f(n-2)+2g(n-2),

(3)

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

f(n)=10f(n-1)+15f(n-2)+10g(n-2),

(4)

由式(2),得

f(n-1)=5f(n-2)+5g(n-2),

(5)

由式(4)和(5)消去g(n-2),得

f(n)=12f(n-1)+5f(n-2).

(6)

由图4知,f(1)=10.

图4 图G2Fig.4 Figure of G2

由图5知,g(1)=15.

所以由式(2),得f(2)=125.

图5 图G3Fig.5 Figure of G3

定理2设图2-nZ3的完美对集数为φ(n),则

证明容易看出图2-nZ3有完美对集. 为了计算φ(n)的表达式,先定义一个图G4. 把路wt的端点w,t分别与图2-nZ3的顶点u11,u13连接一条边得到的图记为G4,如图6所示.

图6 图G4Fig.6 Figure of G4

容易看出图G4有完美对集. 设图G4的完美对集数为h(n),图G4的完美对集集合为N,按照N中元素饱和顶点w的情况可分两类:设N中包含边wt的完美对集集合为N1,N中包含边wu11的完美对集集合为N2,根据不同完美对集的定义知,N1∩N2=φ,N=N1∪N2,故h(n)=|N|=|N1|+|N2|.

因为wt∈N1,故wu11,tu13∉N1,由φ(n)的定义知,|N1|=φ(n).

因为wu11∈N1,所以tu13,v11v13,v12u12∈N2,由φ(n)的定义知,|N2|=φ(n-1).

故

h(n)=φ(n)+φ(n-1).

(7)

再求φ(n)的递推式. 设图2-nZ3的完美对集集合为N,图2-nZ3包含边u13u11,u13v13,u13u12的完美对集集合分别为N1,N2,N3,则Ni∩Nj=φ(1≤i

因为u11u13∈N1,故v11v13,v12u12∈N1,由φ(n)的定义知,|N1|=φ(n-1).

故|N2|=φ(n-1)+h(n-1).

因为u13u12∈N3,故v12v13,u11v11∈N3,由φ(n)的定义知,|N3|=φ(n-1).

所以

φ(n)=3φ(n-1)+h(n-1).

(8)

由式(7)和(8),得

φ(n)=4φ(n-1)+φ(n-2).

(9)

由图7知,φ(1)=4.

图7 图G5Fig.7 Figure of G5

由图8知,h(1)=5.

图8 图G6Fig.8 Figure of G6

由式(8),得φ(2)=17.