Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges

DOI10.1016/J.EJC.2014.11.001MaRDI QIDQ482134zbMATH OpenOpenAlexFDO

Authors Z. Tajfirouz, M. Aghabali, S. Akbari, S. Friedland, Klas Markström

Publication date 19 December 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.5634

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

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

• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• 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
• On the number of matchings in regular graphs
• The maximum number of perfect matchings in graphs with a given degree sequence
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices

Cited in

(6)

• On the number of Sudoku squares
• On the upper bounds of the numbers of perfect matchings in graphs with given parameters
• Upper bounds for perfect matchings in Pfaffian and planar graphs
• The maximum number of perfect matchings in graphs with a given degree sequence
• On the number of perfect matchings in a bipartite graph
• The 2-factor polynomial detects even perfect matchings

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)