A bound on the number of perfect matchings in Klee-graphs
Marek Cygan, Marcin Pilipczuk, Riste Škrekovski
Abstract
The famous conjecture of Lovász and Plummer, very recently
proven by Esperet et al. (2011), asserts that every cubic bridgeless
graph has exponentially many perfect matchings. In this paper we
improve the bound of Esperet et al. for a specific subclass of cubic
bridgeless graphs called the Klee-graphs. We show that every
Klee-graph with n ≥8 vertices has at least 3
·2(n+12)/60 perfect matchings.
Full Text: PDF PostScript