Blockers and transversals

Given an undirected graph G = ( V , E ) with matching number ν ( G ) , we define d -blockers as subsets of edges B such that ν ( ( V , E ∖ B ) ) ≤ ν ( G ) − d . We define d -transversals T as subsets of edges such that every maximum matching M has | M ∩ 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.