# Blockers and transversals

2009
Published in:
• Discrete Mathematics. - 2009, vol. 309, p. 4306-4314
##### Complete bipartite graph
English Given an undirected graph G=(V,E) with matching number \nu(G), we define d- blockers as subsets of edges B such that \nu(G=(V,E\B))\leq \nu(G)-d. We define d- transversals T as subsets of edges such that every maximum matching M has |M\cap T|\geq 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.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
• English
Classification
Computer science