Marek Cygan ; Marcin Pilipczuk ; Riste Škrekovski - A bound on the number of perfect matchings in Klee-graphs

dmtcs:633 - Discrete Mathematics & Theoretical Computer Science, January 28, 2013, Vol. 15 no. 1 -
A bound on the number of perfect matchings in Klee-graphsArticle

Authors: Marek Cygan ORCID1; Marcin Pilipczuk 1; Riste Škrekovski ORCID2

  • 1 Faculty of Mathematics, Informatics, and Mechanics [Warsaw]
  • 2 Faculty of Mathematics and Physics [Ljubljana]

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.

Volume: Vol. 15 no. 1
Section: Combinatorics
Published on: January 28, 2013
Accepted on: June 9, 2015
Submitted on: August 12, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 347 times.
This article's PDF has been downloaded 464 times.