Blockers and transversals

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.


Published in:
Discrete Mathematics, 309, 13, 4306-4314
Year:
2009
ISSN:
0012-365X
Keywords:
Laboratories:




 Record created 2010-09-30, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)