[CdP18] Minimal graphs for matching extensions

Revue Internationale avec comité de lecture : Journal Discrete Applied Math. , vol. 234, pp. 47-55, 2018, (doi:10.1016/j.dam.2015.11.007)

Mots clés: maximum matching, matching extension, expandable graph, completable graph.

Résumé: Given a positive integer n we find a graph G = (V, E) on |V | = n vertices with a minimum number of edges such that for any pair of non adjacent vertices x, y the graph G − x − y contains a (almost) perfect matching M . Intuitively the non edge xy and M form a (almost) perfect matching of G. Similarly we determine a graph G = (V, E) with a minimum number of edges such that for any matching M of the complement G of G with size ⌊n/ 2 ⌋ − 1, G−V(M ̄) contains an edge e. Here M ̄ and the edge e of G form a (almost) perfect matching of G ̄. We characterize these minimal graphs for all values of n.

Equipe: oc


@article {
title="{Minimal graphs for matching extensions}",
author="M.-C. Costa and D. de Werra and C. Picouleau",
journal="Discrete Applied Math. ",