Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
From MaRDI portal
Publication:482134
DOI10.1016/J.EJC.2014.11.001zbMATH Open1304.05108arXiv1310.5634OpenAlexW2592261830MaRDI QIDQ482134FDOQ482134
S. Friedland, Z. Tajfirouz, S. Akbari, M. Aghabali, Klas Markström
Publication date: 19 December 2014
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: We give an upper bound on the number of perfect matchings in simple graphs with a given number of vertices and edges. We apply this result to give an upper bound on the number of 2-factors in a directed complete bipartite balanced graph on 2n vertices. The upper bound is sharp for n even. For n odd we state a conjecture on a sharp upper bound.
Full work available at URL: https://arxiv.org/abs/1310.5634
Recommendations
- The maximum number of perfect matchings in graphs with a given degree sequence
- On the number of perfect matchings in a bipartite graph
- On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
- On the upper bounds of the numbers of perfect matchings in graphs with given parameters
- Extremal graphs with a given number of perfect matchings
Cites Work
- Title not available (Why is that?)
- Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
- The maximum number of perfect matchings in graphs with a given degree sequence
- On the number of matchings in regular graphs
- A lower bound for the permanent of a doubly stochastic matrix
- Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
Cited In (2)
This page was built for publication: Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482134)
