An improved linear bound on the number of perfect matchings in cubic graphs
From MaRDI portal
Publication:976154
DOI10.1016/J.EJC.2009.11.008zbMATH Open1218.05127arXiv0901.3894OpenAlexW2122238195WikidataQ57601406 ScholiaQ57601406MaRDI QIDQ976154FDOQ976154
L. Esperet, Daniel Král', Riste Škrekovski, Petr Škoda
Publication date: 17 June 2010
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0901.3894
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
- Matching theory
- Graphs with independent perfect matchings
- Maximum matching and a polyhedron with 0,1-vertices
- Matching structure and the matching lattice
- Counting 1-factors in regular bipartite graphs
- Brick decompositions and the matching rank of graphs
- Rank of maximum matchings in a graph
- Perfect matchings in planar cubic graphs
- A New Lower Bound on the Number of Perfect Matchings in Cubic Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
Cited In (7)
- 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
- Exponentially many perfect matchings in cubic graphs
- Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings
- Unions of perfect matchings in cubic graphs
- Title not available (Why is that?)
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)
