Two results on matching extensions with prescribed and proscribed edge sets

被引：10

作者：

Aldred, REL

Holton, DA

Porteous, MI

Plummer, MD

机构：

[1] Univ Otago, Dept Math, Dunedin, New Zealand

[2] Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA

来源：

DISCRETE MATHEMATICS | 1999年 / 206卷 / 1-3期

关键词：

D O I：

10.1016/S0012-365X(98)00405-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a graph with at least 2(m + n + 1) vertices. Then G is E(m,n) if for each pair of disjoint matchings M, N subset of or equal to E(G) of size m and n, respectively, there exists a perfect matching F in G such that M subset of or equal to F and F boolean AND N = 0. In this paper, we prove two results concerning the property E(m, n). The first involves the class of claw-free graphs and the second is a result about bipartite graphs. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：35 / 43

页数：9

共 15 条

[1]

[Anonymous], 1996, C NUMER

[2] Claw-free graphs - A survey [J].

Faudree, R ;

Flandrin, E ;

Ryjacek, Z .

DISCRETE MATHEMATICS, 1997, 164 (1-3) :87-147

[3]

HOLTON DA, 1991, GRAPH THEORY COMBINA, P651

[4]

Konig D., 1916, MATH ANN, V77, P453

[5]

Konig D., 1916, MATH TERMESZETTUDOMA, V34, P453

[6]

LASVERGNAS M, 1975, 1974 C THEOR GRAPH C, V17, P257

[7]

Plummer M.D., 1991, MATCHING EXTENSION R, P416

[8]

Plummer M D., 1986, P 17 SE C COMB GRAPH, P245

[9] ON N-EXTENDABLE GRAPHS [J].

PLUMMER, MD .

DISCRETE MATHEMATICS, 1980, 31 (02) :201-210

[10] EXTENDING MATCHINGS IN CLAW-FREE GRAPHS [J].

PLUMMER, MD .

DISCRETE MATHEMATICS, 1994, 125 (1-3) :301-307

← 1 2 →