Exponentially many perfect matchings in cubic graphs
From MaRDI portal
(Redirected from Publication:555602)
Abstract: We show that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. This confirms an old conjecture of Lovasz and Plummer. This version of the paper uses a different definition of a burl from the journal version of the paper and a different proof of Lemma 18 is given. This simplifies the exposition of our arguments throughout the whole paper.
Cites work
- scientific article; zbMATH DE number 3621721 (Why is no real title available?)
- scientific article; zbMATH DE number 3390835 (Why is no real title available?)
- A bound on the number of perfect matchings in Klee-graphs
- A new lower bound on the number of perfect matchings in cubic graphs
- An improved linear bound on the number of perfect matchings in cubic graphs
- Brick decompositions and the matching rank of graphs
- Counting 1-factors in regular bipartite graphs
- Explicit construction of regular graphs without small cycles
- Fullerene graphs have exponentially many perfect matchings
- Matching theory
- Maximum matching and a polyhedron with 0,1-vertices
- On Leonid Gurvits's proof for permanents
- Perfect matchings in planar cubic graphs
- Rank of maximum matchings in a graph
- The complexity of computing the permanent
Cited in
(27)- Expressions for the perfect matching numbers of cubic l m 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
- Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
- Non-degenerated ground states and low-degenerated excited states in the antiferromagnetic Ising model on 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
- Complete forcing numbers of catacondensed hexagonal systems
- Perfect matching in bipartite hypergraphs subject to a demand graph
- Counting circuit double covers
- 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
- scientific article; zbMATH DE number 5130820 (Why is no real title available?)
- The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
- 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)
