An improved linear bound on the number of perfect matchings in cubic graphs
Author/Authors :
Esperet، نويسنده , , Louis and Kr?l’، نويسنده , , Daniel and ?koda، نويسنده , , Petr and ?krekovski، نويسنده , , Riste، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Pages :
19
From page :
1316
To page :
1334
Abstract :
We show that every cubic bridgeless graph with n vertices has at least 3 n / 4 − 10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope.
