The 2-Extendability of Graphs on the Projective Plane, the Torus and the Klein Bottle

被引：7

作者：

Mizukai, Iwao ^{[2
]}

Negami, Seiya ^{[1
]}

Suzuki, Yusuke ^{[3
]}

机构：

[1] Yokohama Natl Univ, Fac Educ & Human Sci, Hodogaya Ku, Yokohama, Kanagawa 2408501, Japan

[2] Yokohama Natl Univ, Grad Sch, Dept Informat Media & Environm Sci, Hodogaya Ku, Yokohama, Kanagawa 2408501, Japan

[3] Tsuruoka Natl Coll Technol, Yamagata 9978511, Japan

来源：

GRAPHS AND COMBINATORICS | 2010年 / 26卷 / 04期

关键词：

Matching extendability; Projective plane; Torus; Klein bottle; SURFACES; GENUS;

D O I：

10.1007/s00373-010-0927-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph is said to be k-extendable if any independent set of k edges extends to a perfect matching. We shall show that every 5-connected graph of even order embedded on the projective plane and every 6-connected one embedded on the torus and the Klein bottle is 2-extendable and characterize the forbidden structures for 5-connected toroidal graphs to be 2-extendable.

引用

页码：549 / 557

页数：9