Université de Fribourg

Blockers and transversals

Zenklusen, Rico ; Ries, Bernard ; Picouleau, Christophe ; de Werra, Dominique ; Costa, Marie-Christine ; Bentz, Cédric

In: Discrete Mathematics, 2009, vol. 309, p. 4306-4314

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