Exponentially many perfect matchings in cubic graphs
From MaRDI portal
Publication:555602
DOI10.1016/j.aim.2011.03.015zbMath1223.05229arXiv1012.2878OpenAlexW1982321501WikidataQ56032470 ScholiaQ56032470MaRDI QIDQ555602
Louis Esperet, Serguei Norine, Andrew D. King, František Kardoš, 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
Related Items (21)
Nice pairs of odd cycles in fullerene graphs ⋮ Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations ⋮ Shortest perfect pseudomatchings in fullerene graphs ⋮ Factorially many maximum matchings close to the Erdős-Gallai bound ⋮ Average connectivity and average edge-connectivity in graphs ⋮ Connected cubic graphs with the maximum number of perfect matchings ⋮ The extendability of matchings in strongly regular graphs ⋮ Perfect matching in bipartite hypergraphs subject to a demand graph ⋮ Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching ⋮ Non-degenerated ground states and low-degenerated excited states in the antiferromagnetic Ising model on triangulations ⋮ Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings ⋮ An equivalent formulation of the Fan-Raspaud Conjecture and related problems ⋮ A bound for the number of vertices of a polytope with applications ⋮ Uniform generation of \(d\)-factors in dense host graphs ⋮ Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows ⋮ Polynomial degeneracy for the first \(m\) energy levels of the antiferromagnetic Ising model ⋮ Three-dimensional right-angled polytopes of finite volume in the Lobachevsky space: combinatorics and constructions ⋮ Computing the Partition Function for Perfect Matchings in a Hypergraph ⋮ On the expected number of perfect matchings in cubic planar graphs ⋮ Counting perfect matchings in the geometric dual ⋮ Complete forcing numbers of catacondensed hexagonal systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Explicit construction of regular graphs without small cycles
- Fullerene graphs have exponentially many perfect matchings
- An improved linear bound on the number of perfect matchings in cubic graphs
- Brick decompositions and the matching rank of graphs
- Matching theory
- Counting 1-factors in regular bipartite graphs
- Perfect matchings in planar cubic graphs
- On Leonid Gurvits’s Proof for Permanents
- 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
This page was built for publication: Exponentially many perfect matchings in cubic graphs
