Algorithms for (0, 1, d)-graphs with d constrains

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.