Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
2015 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 45, 132-144 p.Article in journal (Refereed) Published
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 even n. For odd n we state a conjecture on a sharp upper bound.
Place, publisher, year, edition, pages
2015. Vol. 45, 132-144 p.
IdentifiersURN: urn:nbn:se:umu:diva-99326DOI: 10.1016/j.ejc.2014.11.001ISI: 000348746000013ScopusID: 2-s2.0-84914161777OAI: oai:DiVA.org:umu-99326DiVA: diva2:786803