| 杨利民,年四洪.无 K3子图的图中1-因子计数[J].,2021,61(5):546-550 |
| 无 K3子图的图中1-因子计数 |
| Counting of 1-factors in graphs without K3 subgraphs |
| |
| DOI：10.7511/dllgxb202105014 |
| 中文关键词: N(G，k) 色多项式 S(n)-因子 1-因子 |
| 英文关键词: N(G, k) chromatic polynomial S(n)-factor 1-factor |
| 基金项目:大理大学高层次人才科研启动基金资助项目(KY0719203410). |
|
| 摘要点击次数: 252 |
| 全文下载次数: 158 |
| 中文摘要: |
| 1-因子或完美匹配的计数是NP 难的，利用S(n)-因子的表示公式和分支分析方法研究1-因子或完美匹配具有理论和实际意义．首先，得到无K3子图的图中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 K3 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. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |