Minimal graphs for matching extensions

Marie-Christine Costa, Dominique de Werra and Picouleau Christophe

2018

Publication type:

Paper in peer-reviewed journals

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

Keywords :

Maximum matching; Matching extension; Expandable graph; Completable graph

Abstract:

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},
}