Orthogonal matchings

被引：11

作者：

Anstee, RP

Caccetta, L

机构：

[1] Univ British Columbia, Dept Math, Vancouver, BC V6T 1Z2, Canada

[2] Curtin Univ Technol, Dept Math & Stat, Perth, WA 6001, Australia

来源：

DISCRETE MATHEMATICS | 1998年 / 179卷 / 1-3期

关键词：

matching; orthogonal matching; transversal;

D O I：

10.1016/S0012-365X(97)00025-3

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Consider a graph G which is a union of m spanning subgraphs regular of degree k. We show that for k greater than or equal to 3 there is a matching of size m which uses exactly one edge from each subgraph. A problem of Alspach asks whether this is true for k=2. We find a matching of size m-m(2/3) (for large m) when k=2, using at most one edge from each subgraph and for k=1 we get a matching of size m-3/2m(2/3) (for large m). ,For subgraphs regular of degree I (i.e. perfect matchings) and G being the complete bipartite graph K-m,K-m,,, a matching with one edge from each factor corresponds to a transversal in a Latin square.

引用

页码：37 / 47

页数：11

共 6 条

[1]

Alspach B., 1988, DISCRETE MATH, V69, P106

[2]

Brouwer A.E., 1978, NIEUW ARCH WISKD, V26, P330

[3]

Caccetta L., 1992, AUSTRALAS J COMB, V5, P229

[4] ON THE EXISTENCE OF A MATCHING ORTHOGONAL TO A 2-FACTORIZATION [J].