Edge proximity and matching extension in projective planar graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Edge proximity and matching extension in projective planar graphs

Authors:	Jun Fujisawa Hiroki Seno

Institution:	1. Faculty of Business and Commerce, Keio University, Yokohama, Japan;2. Graduate School of Environment and Information Science, Yokohama National University, Yokohama, Japan

Abstract:	A graph $G$ with at least $2 ? m + 2$ vertices is said to be distance $d$ $m$ -extendable if, for any matching $M$ of $G$ with $m$ edges in which the edges lie at distance at least $d$ pairwise, there exists a perfect matching of $G$ containing $M$ . In this paper we prove that every 5-connected triangulation on the projective plane of even order is distance 3 7-extendable and distance 4 $m$ -extendable for any $m$ .

Keywords:	edge proximity matching extension projective plane graph triangulation