Title of article :
Cubic bridgeless graphs have more than a linear number of perfect matchings
Author/Authors :
Esperet، نويسنده , , Louis and Kardo?، نويسنده , , Franti?ek and Kr?lʹ، نويسنده , , Daniel، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Abstract :
Lovلsz and Plummer conjectured in the 1970ʹs that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve (1979), and for planar graphs by Chudnovsky and Seymour (2008). In this paper, we provide the first superlinear bound in the general case.
Keywords :
Perfect matchings , cubic graphs
Journal title :
Electronic Notes in Discrete Mathematics
Journal title :
Electronic Notes in Discrete Mathematics