[CdP18] Minimal graphs for matching extensions

Revue Internationale avec comité de lecture : Journal Discrete Applied Math. , vol. 234, pp. 47-55, 2018, (doi:10.1016/j.dam.2015.11.007)

Auteurs: M.-C. Costa , D. de Werra , C. Picouleau

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:

Download

BibTeX

@article {
	CdP18,
	title	=	"{Minimal graphs for matching extensions}",
	author	=	"M.-C. Costa and D. de Werra and C. Picouleau",
	journal	=	"Discrete Applied Math. ",
	year	=	2018,
	volume	=	234,
	pages	=	"47-55",
	doi	=	"10.1016/j.dam.2015.11.007",
}