The Number of Perfect Matchings in Two Types of 3-Regular Graph
返回论文页
|更新时间:2023-12-11
|
The Number of Perfect Matchings in Two Types of 3-Regular Graph
Acta Scientiarum Naturalium Universitatis SunYatseniVol. 53, Issue 5, Pages: 54-58(2014)
作者机构:
1. 天水师范学院数学与统计学院,甘肃,天水,741001
2.
作者简介:
基金信息:
DOI:
CLC:
Published:2014,
Published Online:25 September 2014,
扫 描 看 全 文
TANG Baoxiang, REN Han. The Number of Perfect Matchings in Two Types of 3-Regular Graph. [J]. Acta Scientiarum Naturalium Universitatis SunYatseni 53(5):54-58(2014)
DOI:
TANG Baoxiang, REN Han. The Number of Perfect Matchings in Two Types of 3-Regular Graph. [J]. Acta Scientiarum Naturalium Universitatis SunYatseni 53(5):54-58(2014)DOI:
The Number of Perfect Matchings in Two Types of 3-Regular Graph
It's an important application for perfect matching counting theories in quantum chemistry
crystal physics and computer science. The research for perfect matching counting theories has a quite important theoretical value and realistic meanings. But the counting problem of perfect matching for general graphs has been proved to be NP—hard. Lovász and Plummer proposed a conjecture on this problem: every 2-edge-connected cubic graph has at least exponential perfect matchings. By applying differentiation
summation and re-nested recursive calculation
several counting formulas of the perfect matching for two specific types of graphs are given. And the results indicate that the conjecture of Lovász and Plummer is true in the case of these two types of graphs.