Zenklusen, R., Ries, B., Picouleau, C., de Werra, D., Costa, M., and Bentz, C. (2009)

Blockers and transversals, Discrete Mathematics 309(13):4306-4314.

Given 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.

doi:10.1016/j.disc.2009.01.006 (click here for the full paper)