[CdP15] Minimal graphs for matching extensions

Revue Internationale avec comité de lecture : Journal Discrete Applied Math. , pp. 1-9. Available online., 2015, (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
Collaboration:

BibTeX

 @article { CdP15, title = "{Minimal graphs for matching extensions}", author = "M.-C. Costa and D. de Werra and C. Picouleau", journal = "Discrete Applied Math. ", year = 2015, pages = "1-9. Available online.", doi = "10.1016/j.dam.2015.11.007", }