EXTENDING MATCHINGS IN CLAW-FREE GRAPHS

被引：24

作者：

PLUMMER, MD

机构：

[1] Department of Mathematics, Vanderbilt University, Nashville

来源：

DISCRETE MATHEMATICS | 1994年 / 125卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(94)90171-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a graph with a perfect matching and let n be an integer, 1 less than or equal to n < \V(G)1/2. Graph G is n-extendable if every matching of size n in G is a subset of a perfect matching. Graph G is bicritical if G-u-v has a perfect matching for every pair of points u and v in V(G). It is proved that every 3-connected claw-free graph is bicritical and for n greater than or equal to 2, every (2n + 1)-connected claw-free graph is n-extendable. Matching extension in planar and toroidal claw-free graphs is then considered.

引用

页码：301 / 307

页数：7

共 20 条

[1] CLAW-FREE GRAPHS ARE EDGE RECONSTRUCTIBLE [J].