Journal
DISCRETE MATHEMATICS
Volume 309, Issue 13, Pages 4306-4314Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disc.2009.01.006
Keywords
Transversal; Blocker; Matching; Complete graph; Complete bipartite graph
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available