无K3子图的图中1-因子计数

杨 利 民，年 四 洪

(1.大理大学 数学与计算机学院,云南 大理 671003；2.大连理工大学 数学科学学院,辽宁 大连 116024)

0 引 言

1-因子或完美匹配在量子化学、晶体物理学和计算机领域中有重要应用．1-因子或完美匹配是覆盖图的所有顶点的不交边的集合．Tutte在1947年给出1-因子或完美匹配存在的一个充分必要条件[1]．这个结果是图论中的奠基性的定理，在图论历史上有重要意义，然而如何判断1-因子或完美匹配的存在，仍是一个十分困难的问题．相比之下，计算1-因子的个数是更困难的．S(n)-因子计数理论包括S(n)-因子的表示公式和分支分析方法．通过利用已建立的S(n)-因子计数理论和组合数学方法，可以解决无K3子图的图中1-因子计数．

1 定义和引理

定义1令S(n)={Ki：1≤i≤n}，n≥1，并且Ki是有i个顶点的完全图，如果M是图G的一个子图，且M的任意分支都同构于S(n)={Ki：1≤i≤n}的某一元素，那么M叫作图G的一个S(n)-子图，如果M是图G的一个生成子图，那么M叫作图G的一个S(n)-因子．

恰有k个分支的S(n)-因子的个数记为N(G，k)．

S(n)-因子计数的表示公式如下．

图论中分支分析方法公式如下：

2 主要结果

用f(G)记图G中1-因子的个数．

定理1如果图G是无K3子图或三角形的任意图，那么f(G)=N(G,n/2)．

证明因为图G是无K3子图或三角形的任意图，所以它就没有K4，K5，…，Kn子图，从而S(n)-因子的元素只能是K1或K2，即每一个元素是顶点或边．N(G,n/2)是恰有n/2个分支的S(n)-因子的个数，N(G,n/2)的每一分支都是K2，即边，而1-因子是覆盖图G的不交边的集合，所以有公式f(G)=N(G,n/2)．

□

其中S(p,n/2)是第二类Stirling数．

因为图G是无K3子图或三角形，根据定理1，得到f(G)=N(G,n/2)，所以无K3子图的……