https://hal.inria.fr/hal-00990605Cygan, MarekMarekCyganMIMUW - Faculty of Mathematics, Informatics, and Mechanics [Warsaw] - UW - University of WarsawPilipczuk, MarcinMarcinPilipczukMIMUW - Faculty of Mathematics, Informatics, and Mechanics [Warsaw] - UW - University of WarsawŠkrekovski, RisteRisteŠkrekovskiFMF - Faculty of Mathematics and Physics [Ljubljana] - University of Ljubljana A bound on the number of perfect matchings in Klee-graphsHAL CCSD2013[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Inria Sophia Antipolis-Méditerranée / I3s, Service Ist2014-05-13 16:28:482020-06-08 09:48:022014-05-13 16:46:34enJournal articleshttps://hal.inria.fr/hal-00990605/document10.46298/dmtcs.633application/pdf1The 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.