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. (C) 2014 Elsevier Ltd. All rights reserved.
引用
收藏
页码:132 / 144
页数:13
相关论文
共 6 条
[1]
Alon N, 2008, ELECTRON J COMB, V15
[2]
[Anonymous], ELECT J COMBIN
[3]
BREGMAN LM, 1973, DOKL AKAD NAUK SSSR+, V211, P27