[PDC14] Minimum size extensible graphs for (near) perfect matchings

Conférence Internationale avec comité de lecture : International Conference on Graph Theory, April 2014, pp.juin 2014, Grenoble, France,

Mots clés: matching, extensible set

Résumé: We define as extensible a graph G such that for every pair u,v of non adjacent vertices it is possible to extend the non-edge uv to a perfect (or near perfect) matching using only edges of G that are not incident to u or v. For every order n of G we give Ext(n) the minimum size of an extensible graph.

Equipe: oc


@inproceedings {
title="{Minimum size extensible graphs for (near) perfect matchings}",
author=" C. Picouleau and D. de Werra and M.-C. Costa ",
booktitle="{International Conference on Graph Theory}",
pages="juin 2014",
address="Grenoble, France",