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

DOI10.1016/J.EJC.2009.11.008MaRDI QIDQ976154zbMATH OpenOpenAlexWikidataFDO

Authors L. Esperet, Daniel Král', Petr Škoda, Riste Škrekovski

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

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

Abstract: We show that every cubic bridgeless graph with n vertices has at least 3n/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.

Recommendations

• A new lower bound on the number of perfect matchings in cubic graphs
• Cubic bridgeless graphs have more than a linear number of perfect matchings
• A superlinear bound on the number of perfect matchings in cubic bridgeless graphs
• Connected cubic graphs with the maximum number of perfect matchings
• Covering a cubic graph with perfect matchings

Cites work

• scientific article; zbMATH DE number 3704754 (Why is no real title available?)
• scientific article; zbMATH DE number 3621721 (Why is no real title available?)
• A new lower bound on the number of perfect matchings in cubic graphs
• Brick decompositions and the matching rank of graphs
• Concerning a Conjecture of Marshall Hall
• Counting 1-factors in regular bipartite graphs
• Graphs with independent perfect matchings
• Matching structure and the matching lattice
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• On Lower Bounds for Permanents of (0, 1) Matrices
• On the Permanent of a Certain Class of (0, 1)-Matrices
• Perfect matchings in planar cubic graphs
• Rank of maximum matchings in a graph

Cited in

(13)

• A superlinear bound on the number of perfect matchings in cubic bridgeless graphs
• Perfect matchings with restricted intersection in cubic graphs
• Connected cubic graphs with the maximum number of perfect matchings
• The cost of perfection for matchings in graphs
• Exponentially many perfect matchings in cubic graphs
• A new lower bound on the number of perfect matchings in cubic graphs
• Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings
• On the expected number of perfect matchings in cubic planar graphs
• A bound on the number of perfect matchings in Klee-graphs
• Unions of perfect matchings in cubic graphs
• Cubic bridgeless graphs have more than a linear number of perfect matchings
• Enumerating perfect matchings of a Halin graph
• scientific article; zbMATH DE number 5130820 (Why is no real title available?)

This page was built for publication: An improved linear bound on the number of perfect matchings in cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976154)