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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.37--52
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990605
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:28:48
Dernière modification le : jeudi 7 septembre 2017 - 01:03:39
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:44:57

Fichier

1696-7669-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990605, version 1

Collections

Citation

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. 〈hal-00990605〉

Partager

Métriques

Consultations de la notice

203

Téléchargements de fichiers

196