Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649637 | Discrete Mathematics | 2009 | 9 Pages |
Abstract
Given an undirected graph G=(V,E)G=(V,E) with matching number ν(G)ν(G), we define dd-blockers as subsets of edges BB such that ν((V,E∖B))≤ν(G)−dν((V,E∖B))≤ν(G)−d. We define dd-transversals TT as subsets of edges such that every maximum matching MM has |M∩T|≥d|M∩T|≥d. We explore connections between dd-blockers and dd-transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum dd-transversals and dd-blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
R. Zenklusen, B. Ries, C. Picouleau, D. de Werra, M.-C. Costa, C. Bentz,