Distance-restricted matching extension in triangulations of the torus and the Klein bottle

R. E.L. Aldred, Jun Fujisawa

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Issue number3
Publication statusPublished - 2014 Sept 18


  • Distance restricted matching extension
  • Klein bottle graph
  • Non-contractible cycle
  • Separating cycle
  • Toroidal graph
  • Triangulation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Distance-restricted matching extension in triangulations of the torus and the Klein bottle'. Together they form a unique fingerprint.

Cite this