完全图的因子计数

The Factor Enumeration of Complete Graph Kn

一个图H称为一个双星 (DoubleStar) ,当H由 2个不交的星K1,m1 、K1,m2 加上连接它们最大度点的一条边所构成 .图G的一个支撑子图F称为一个双星 (DS)因子 ,当F的每一个连通分支是一个双星 .若F的每一个连通分支是路 ,圈或顶点数大于等于 4的星 ,则称F为G的一个PCS -因子 .完全图Kn存在DS -因子和PCS-因子 ,它们的计数公式分别由定理 1和定理

A graph H is said to be a double star(simply DS)if H consists of two disjoint stars K 1,m 1 ,K 1,m 2 together with an edge between a vertex in K 1,m 1 anda vertex in K 1,m 2 which have the maximum degrees in K 1,m 1 and K 1,m 2 respectivˉely.A spanning subˉgraph F of a graph G is said to be a DSˉfactor if every connected component of F is a DS.F is said to be a PCSˉfactor if every connected component of F is a path or a cycle or a star with four or over four vertexes.Comˉplete graph Kn has DSˉfactor and PCSˉfactor,whose formulas of enumeration are give by theorem1and theorem2.