Abstract
Let G be a graph with vertex set V(G). Let n, k, d be non-negative integers such that n+2k+d≤|V(G)|−2 and |V(G)|−n−d are even. A matching which saturates exactly |V(G)|−d vertices is called a defect-d matching of G. If when deleting any n vertices the remaining subgraph contains a matching of k edges and every k-matching can be extended to a defect-d matching, then G is said to be an (n, k, d)-graph. We present an algorithm to determine (0, 1, d)-graphs with d constraints. Moreover, we solve the problem of augmenting a bipartite graph G=(B, W) to be a (0, 1, d)-graph by adding fewest edges, where d=∥B|−|W∥. The latter problem is applicable to the job assignment problem, where the number of jobs does not equal the number of persons.
Acknowledgements
The authors are grateful to the referees for many valuable suggestions. In particular, their helpful comments improve the presentation of the paper.