Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

A bound on the number of perfect matchings in Klee-graphs

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 4:28:48 PM
Last modification on : Monday, June 8, 2020 - 9:48:02 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:44:57 PM


Files produced by the author(s)




Marek Cygan, Marcin Pilipczuk, Riste Škrekovski. A bound on the number of perfect matchings in Klee-graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.37--52. ⟨10.46298/dmtcs.633⟩. ⟨hal-00990605⟩



Record views


Files downloads