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 = parallel to B| - |W parallel to. The latter problem is applicable to the job assignment problem, where the number of jobs does not equal the number of persons.