Publication
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)) = 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.