An improved linear bound on the number of perfect matchings in cubic graphs

DOI10.1016/j.ejc.2009.11.008zbMath1218.05127arXiv0901.3894WikidataQ57601406 ScholiaQ57601406MaRDI QIDQ976154

Riste Škrekovski, Louis Esperet, Daniel Král', Petr Škoda

Publication date: 17 June 2010

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0901.3894

zbMATH Keywords

perfect matching polytope

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

A superlinear bound on the number of perfect matchings in cubic bridgeless graphs, Exponentially many perfect matchings in cubic graphs, Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Brick decompositions and the matching rank of graphs
• Matching theory
• Matching structure and the matching lattice
• Counting 1-factors in regular bipartite graphs
• Perfect matchings in planar cubic graphs
• Graphs with independent perfect matchings
• A New Lower Bound on the Number of Perfect Matchings in Cubic Graphs
• Rank of maximum matchings in a graph
• Maximum matching and a polyhedron with 0,1-vertices
• Concerning a Conjecture of Marshall Hall
• On Lower Bounds for Permanents of (0, 1) Matrices
• On the Permanent of a Certain Class of (0, 1)-Matrices