Exponentially many perfect matchings in cubic graphs
DOI10.1016/J.AIM.2011.03.015zbMATH Open1223.05229arXiv1012.2878OpenAlexW1982321501WikidataQ56032470 ScholiaQ56032470MaRDI QIDQ555602FDOQ555602
Authors: L. Esperet, František Kardoš, Andrew D. King, Serguei Norine, Daniel Král' 
Publication date: 25 July 2011
Published in: Advances in Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.2878
cubic graphperfect matching[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Lov%EF%BF%BD%EF%BF%BDsz-Plummer+conjecture&go=Go Lov��sz-Plummer conjecture]perfect matching polytope
Cites Work
- Matching theory
- The complexity of computing the permanent
- Maximum matching and a polyhedron with 0,1-vertices
- 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?)
- An improved linear bound on the number of perfect matchings in cubic graphs
- Explicit construction of regular graphs without small cycles
- Fullerene graphs have exponentially many perfect matchings
- On Leonid Gurvits's proof for permanents
- A bound on the number of perfect matchings in Klee-graphs
Cited In (27)
- Expressions for the perfect matching numbers of cubic \(l\times m\times n\) lattices and their asymptotic values
- Three-dimensional right-angled polytopes of finite volume in the Lobachevsky space: combinatorics and constructions
- Nice pairs of odd cycles in fullerene graphs
- The extendability of matchings in strongly regular graphs
- A superlinear bound on the number of perfect matchings in cubic bridgeless graphs
- Connected cubic graphs with the maximum number of perfect matchings
- A bound for the number of vertices of a polytope with applications
- Non-degenerated ground states and low-degenerated excited states in the antiferromagnetic Ising model on triangulations
- Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
- Factorially many maximum matchings close to the Erdős-Gallai bound
- The expected number of perfect matchings in cubic planar graphs
- Polynomial degeneracy for the first \(m\) energy levels of the antiferromagnetic Ising model
- Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings
- On the expected number of perfect matchings in cubic planar graphs
- Computing the partition function for perfect matchings in a hypergraph
- Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows
- An equivalent formulation of the Fan-Raspaud conjecture and related problems
- Perfect matching in bipartite hypergraphs subject to a demand graph
- Counting circuit double covers
- Complete forcing numbers of catacondensed hexagonal systems
- Shortest perfect pseudomatchings in fullerene graphs
- Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
- Counting perfect matchings in the geometric dual
- Uniform generation of \(d\)-factors in dense host graphs
- The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
- Title not available (Why is that?)
- Average connectivity and average edge-connectivity in graphs
This page was built for publication: Exponentially many perfect matchings in cubic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q555602)
