Minimal graphs for matching extensions

Marie-Christine Costa, Dominique de Werra and Picouleau Christophe
Publication type:
Paper in peer-reviewed journals
Discrete Applied Math., vol. available online
Keywords :
Maximum matching; Matching extension; Expandable graph; Completable graph
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 Ḡ of G with size ⌊n2⌋−1, G−V(M̄) contains an edge e. Here M̄ and the edge e of G form a (almost) perfect matching of Ḡ. We characterize these minimal graphs for all values of n.
    author={Marie-Christine Costa and Dominique de Werra and Picouleau 
           Christophe },
    title={Minimal graphs for matching extensions },
    doi={10.1016/j.dam.2015.11.007 },
    journal={Discrete Applied Math. },
    year={2016 },
    volume={available online },