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

  • Robert E.L. Aldred
  • Jun Fujisawa
Keywords: distance restricted matching extension, triangulation, toroidal graph, Klein bottle graph, non-contractible cycle, separating cycle


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.

Article Number