无K_(3)子图的图中1-因子计数  

Counting of 1-factors in graphs without K_(3) subgraphs

作　　者：杨利民 年四洪[2] YANG Limin;NIAN Sihong(School of Mathematics and Computer, Dali University, Dali 671003, China;School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China)

机构地区：[1]大理大学数学与计算机学院,云南大理671003 [2]大连理工大学数学科学学院,辽宁大连116024

出　　处：《大连理工大学学报》2021年第5期546-550,共5页Journal of Dalian University of Technology

基　　金：大理大学高层次人才科研启动基金资助项目(KY0719203410).

摘　　要：1-因子或完美匹配的计数是NP-难的,利用S^((n))-因子的表示公式和分支分析方法研究1-因子或完美匹配具有理论和实际意义.首先,得到无K_(3)子图的图中1-因子计数公式和组合恒等式;其次,导出1-因子或完美匹配存在和不存在的充分必要条件;最后,得出一个结论:存在连通图使得它的1-因子的个数大于任意的自然数N.It is NP-hard to count 1-factor or perfect matching.It is of theoretical and practical significance to study 1-factor or perfect matching by using representation formula and branch analysis method of S^((n))-factor.Firstly,the counting formulas and combinatorial identities of 1-factors in graphs without K_(3) subgraphs are obtained.Secondly,the necessary and sufficient conditions for the existence and nonexistence of 1-factors or perfect matching are derived.Finally,a conclusion is given that there exists a connected graph such that the number of 1-factors is greater than any natural number N.

关 键 词：N(G k) 色多项式 S^((n))-因子 1-因子 

分 类 号：O157.1[理学—数学] O157.5[理学—基础数学]