On the matching extendability of graphs in surfaces

被引：16

作者：

Aldred, R. E. L. ^{[1
]}

Kawarabayashi, Ken-ichi ^{[2
]}

Plummer, Michael D. ^{[3
]}

机构：

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

[2] Natl Inst Informat, Chiyoda Ku, Tokyo 1018430, Japan

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

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2008年 / 98卷 / 01期

关键词：

embedded graph; genus; matching; extendability; surface; klein bottle; projective plane; torus;

D O I：

10.1016/j.jctb.2007.06.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G with at least 2n + 2 vertices is said to be n-extendable if every matching of size n in G extends to a perfect matching. It is shown that (1) if a graph is embedded on a surface of Euler characteristic X, and the number of vertices in G is large enough, the graph is not 4-extendable; (2) given g > 0, there are infinitely many graphs of orientable genus g which are 3-extendable, and given (g) over bar >= 2, there are infinitely many graphs of non-orientable genus (g) over bar which are 3-extendable; and (3) if G is a 5-connected triangulation with an even number of vertices which has genus g > 0 and sufficiently large representativity, then it is 2-extendable. (c) 2007 Elsevier Inc. All rights reserved.

引用

页码：105 / 115

页数：11

共 16 条

[1]

[Anonymous], 1989, DISCRETE MATH

[2] THE MATCHING EXTENDIBILITY OF SURFACES [J].