Minimal graphs for matching extensions
2018
Publication type:
Paper in peer-reviewed journals
Journal:
Discrete Applied Math., vol. 234, pp. 47--55
Download:
ISBN:
http://dx.doi.org/10.1016/j.dam.2015.11.007
HAL:
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 Ḡ 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.
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}, }