Back to Search Start Over

The number of perfect matchings in a brick

Authors :
Lu, Fuliang
Pan, Huali
Publication Year :
2024

Abstract

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.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2409.14787
Document Type :
Working Paper