The number of perfect matchings in a brick
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913513395453952 |
|---|---|
| author | Lu, Fuliang Pan, Huali |
| author_facet | Lu, Fuliang Pan, Huali |
| contents | A 3-connected graph is a brick if the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of the matching decomposition procedure of Kotzig, and Lovasz and Plummer. Lucchesi and Murty conjectured that there exists a positive integer N such that for every n>N, every brick on n vertices has at least n-1 perfect matchings. We present an infinite family of bricks such that for each even integer n (n > 17), there exists a brick with n vertices in this family that contains [0:625n] perfect matchings, showing that this conjecture fails. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14787 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The number of perfect matchings in a brick Lu, Fuliang Pan, Huali Combinatorics A 3-connected graph is a brick if the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of the matching decomposition procedure of Kotzig, and Lovasz and Plummer. Lucchesi and Murty conjectured that there exists a positive integer N such that for every n>N, every brick on n vertices has at least n-1 perfect matchings. We present an infinite family of bricks such that for each even integer n (n > 17), there exists a brick with n vertices in this family that contains [0:625n] perfect matchings, showing that this conjecture fails. |
| title | The number of perfect matchings in a brick |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.14787 |