Counting perfect matchings in n-extendable graphs

被引：1

作者：

Doslic, Tomislav ^{[1
]}

机构：

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

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 11期

关键词：

n-extendable graph; perfect matching; enumeration;

D O I：

10.1016/j.disc.2006.08.011

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least F(n + 1)!/4[q - p - (n - 1)(2 Delta - 3) + 4]] different perfect matchings, where A is the maximum degree of a vertex in G. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：2297 / 2300

页数：4

共 50 条

[1] ON N-EXTENDABLE GRAPHS
PLUMMER, MD
DISCRETE MATHEMATICS, 1980, 31 (02) : 201 - 210
[2] Hamiltonian cycles in n-extendable graphs
Kawarabayashi, K
Ota, K
Saito, A
JOURNAL OF GRAPH THEORY, 2002, 40 (02) : 75 - 82
[3] Independence number in n-extendable graphs
Maschlanka, P
Volkmann, L
DISCRETE MATHEMATICS, 1996, 154 (1-3) : 167 - 178
[4] Independence number in n-extendable graphs
Discrete Math, 1-3 (167):
[5] On defect n-extendable bipartite graphs
Wen, Xuelian
IMECS 2007: International Multiconference of Engineers and Computer Scientists, Vols I and II, 2007, : 2347 - 2352
[6] Hamilton Cycles in n-Extendable Bipartite Graphs
Li, Yueping
Lou, Dingjun
ARS COMBINATORIA, 2018, 139 : 3 - 18
[7] A novel characterization of n-extendable bipartite graphs
Lin, Hong
Guo, Xiaofeng
ARS COMBINATORIA, 2009, 91 : 353 - 362
[8] On the structure of minimally n-extendable bipartite graphs
Lou, DJ
DISCRETE MATHEMATICS, 1999, 202 (1-3) : 173 - 181
[9] Characterizing minimally n-extendable bipartite graphs
Lou, Dingjun
DISCRETE MATHEMATICS, 2008, 308 (11) : 2269 - 2272
[10] Hamilton Paths in n-Extendable Bipartite Graphs
Gan, Zhiyong
Lou, Dingjun
ARS COMBINATORIA, 2021, 154 : 3 - 21

← 1 2 3 4 5 →