Cygan, Marek and Pilipczuk, Marcin and Škrekovski, Riste - 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-graphs

Authors: Cygan, Marek and Pilipczuk, Marcin and Škrekovski, Riste

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.


Source : oai:HAL:hal-00990605v1
Volume: Vol. 15 no. 1
Section: Combinatorics
Published on: January 28, 2013
Submitted on: August 12, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 37 times.
This article's PDF has been downloaded 72 times.