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

被引：7

作者：

Aaghabali, M. ^{[3
]}

Akbari, S. ^{[1
,4
]}

Friedland, S. ^{[2
]}

Markstroem, K. ^{[5
]}

Tajfirouz, Z. ^{[3
]}

机构：

[1] Sharif Univ Technol, Dept Math Sci, Tehran, Iran

[2] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL USA

[3] Univ Zanjan, Dept Math, Zanjan, Iran

[4] Inst Studies Theoret Phys & Math IPM, Tehran, Iran

[5] Umea Univ, Dept Math & Math Stat, S-90187 Umea, Sweden

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2015年 / 45卷

基金：

美国国家科学基金会;

关键词：

PERMANENT;

D O I：

10.1016/j.ejc.2014.11.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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