| Autor: |
Wu Tingzeng, Zeng Xiaolin |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Open Mathematics, Vol 22, Iss 1, Pp 1209-1225 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2391-5455 |
| DOI: |
10.1515/math-2024-0060 |
| Popis: |
Counting perfect matchings is an interesting and challenging combinatorial task. It has important applications in statistical physics and chemistry. As the general problem is #P-complete, it is usually tackled by randomized heuristics and approximation schemes. Let GG and HH be two graphs. Denote by G×HG\times H the Cartesian product of graphs GG and HH. The number of perfect matchings of some types of Cartesian product G×HG\times H is investigated by the Pfaffian method, where G≅P2G\cong {P}_{2}, P3{P}_{3}, P4{P}_{4} or C4{C}_{4}, and H≅TH\cong T or HH is a non-bipartite graph with a unique cycle. In this article, we construct a Pfaffian orientation of the graph G×P2G\times {P}_{2}, where GG is a non-bipartite graph with kk odd cycles. We obtain the counting formula on the number of perfect matchings of G×P2G\times {P}_{2}. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
