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

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.

Keywords:

• matching
• extendability
• augmentation
• strong connectivity
• algorithms

2000 AMS Subject Classifications :

• 05C70
• 05C85

Acknowledgements

The authors are grateful to the referees for many valuable suggestions. In particular, their helpful comments improve the presentation of the paper.