Zenklusen, RicoRies, BernardPicouleau, Christophede Werra, DominiqueCosta, Marie-ChristineBentz, Cédric2010-09-302010-09-302010-09-30200910.1016/j.disc.2009.01.006https://infoscience.epfl.ch/handle/20.500.14299/54456WOS:000266760400013Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) <= nu(G) - d. We define d-transversals T as subsets of edges such that every maximum matching M has |M boolean AND T| >= d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum d-transversals and d-blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs. (C) 2009 Elsevier B.V. All rights reserved.TransversalBlockerMatchingComplete graphComplete bipartite graphDeletion ProblemsBipartite GraphsMatchingsComplexitytext::journal::journal article::research article