Geodesic
Distance-restricted matching extension in triangulations of the torus and the Klein bottle
Robert E.L. Aldred1 ; Jun Fujisawa2
1Department of Mathematics and Statistics, University of Otago
2Faculty of Business and Commerce, Keio University
The electronic journal of combinatorics, Tome 21 (2014) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/2952
Classification : 05C70, 05C10, 05C12
Mots-clés : distance-restricted matching extension, triangulation, toroidal graph, Klein-bottle graph, non-contractible cycle, separating cycle

Robert E.L. Aldred  1   ; Jun Fujisawa  2

1 Department of Mathematics and Statistics, University of Otago
2 Faculty of Business and Commerce, Keio University 
@article{10_37236_2952,
     author = {Robert E.L. Aldred and Jun Fujisawa},
     title = {Distance-restricted matching extension in triangulations of the torus and the {Klein} bottle},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {3},
     doi = {10.37236/2952},
     zbl = {1301.05257},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2952/}
}
TY  - JOUR
AU  - Robert E.L. Aldred
AU  - Jun Fujisawa
TI  - Distance-restricted matching extension in triangulations of the torus and the Klein bottle
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2952/
DO  - 10.37236/2952
ID  - 10_37236_2952
ER  - 
%0 Journal Article
%A Robert E.L. Aldred
%A Jun Fujisawa
%T Distance-restricted matching extension in triangulations of the torus and the Klein bottle
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2952/
%R 10.37236/2952
%F 10_37236_2952
Robert E.L. Aldred; Jun Fujisawa. Distance-restricted matching extension in triangulations of the torus and the Klein bottle. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/2952

Cité par Sources :