唐保祥,任 韩

(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的完美……