Minimal graphs for matching extensions

Marie-Christine Costa, Dominique de Werra and Picouleau Christophe

2018

Type de publication :

Article (revues avec comité de lecture)

Journal :

Discrete Applied Math., vol. 234, pp. 47--55

ISBN :

http://dx.doi.org/10.1016/j.dam.2015.11.007

DOI :

10.1016/j.dam.2015.11.007

HAL :

hal-01413150

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 ⌊n2⌋−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.

BibTeX :

@article{Cos-DeW-Chr-2018,
    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={2018 },
    volume={234 },
    pages={47--55},
}