Factor-critical graphs with the minimum number of near-perfect matchings

被引：5

作者：

Doslic, Tomislav ^{[1
]}

Rautenbach, Dieter ^{[2
]}

机构：

[1] Univ Zagreb, Fac Civil Engn, Dept Math, Zagreb 41000, Croatia

[2] Univ Ulm, Inst Optimizat & Operat Res, D-89069 Ulm, Germany

来源：

DISCRETE MATHEMATICS | 2015年 / 338卷 / 12期

关键词：

Matching; Factor-critical; Near-perfect matching;

D O I：

10.1016/j.disc.2015.04.032

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that a factor-critical graph of order n has exactly n near-perfect matchings if and only if it is a connected graph whose blocks are all odd cycles. This characterizes the factor-critical graphs with the minimum number of near-perfect matchings. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：2318 / 2319

页数：2