| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [10 references]
https://hal.inria.fr/hal-00990605
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
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
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
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
File
1696-7669-1-PB.pdf
Files produced by the author(s)