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

2013/10/21 by M. Aaghabali, Aaghabali, M., S. Akbari +7
Mathematics · #05A20 #05C20 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A20 #msc:05C20 #msc:05C70

paper · pdf · doi:10.48550/arxiv.1310.5634

17 pages, 2 tables, 5 figures

arxiv created 2014/07/31 · arxiv updated 2014/08/01

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.

Related

• An upper bound for the number of perfect matchings in graphs
• The maximum number of perfect matchings in graphs with a given degree sequence
• On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
• The maximum number of perfect matchings of semi-regular graphs
• On perfect k-matchings