Distance-Restricted Matching Extension in Triangulations of the Torus and the Klein Bottle

Robert E.L. Aldred, Jun Fujisawa


A graph $G$ with at least $2m+2$ edges is said to be distance $d$ $m$-extendable if for any matching $M$ in $G$ with $m$ edges in which the edges lie pair-wise distance at least $d$, there exists a perfect matching in $G$ containing $M$. In a previous paper, Aldred and Plummer proved that every $5$-connected triangulation of the plane or the projective plane of even order is distance $5$ $m$-extendable for any $m$. In this paper we prove that the same conclusion holds for every triangulation of the torus or the Klein bottle.


distance restricted matching extension; triangulation; toroidal graph; Klein bottle graph; non-contractible cycle; separating cycle

Full Text: