text: Given a family @math of graphs and a positive integer @math , a graph @math is called vertex @math -fault-tolerant with respect to @math , denoted by @math -FT @math , if @math contains some @math as a subgraph, for every @math with @math . Vertex-fault-tolerance has been introduced by Hayes [A graph model for fault-tolerant computing systems, IEEE Transactions on Computers, C-25 (1976), pp. 875-884.], and has been studied in view of potential applications in the design of interconnection networks operating correctly in the presence of faults. We define the Fault-Tolerant Complete Matching (FTCM) Problem in bipartite graphs of order @math : to design a bipartite @math , with @math , @math , @math , that has a FTCM, and the tuple @math , where @math and @math are the maximum degree in @math and @math , respectively, is lexicographically minimum. @math has a FTCM if deleting at most @math vertices from @math creates @math that has a complete matching, i.e., a matching of size @math . We show that if @math is integer, solutions of the FTCM Problem can be found among @math -regular bipartite graphs of order @math , with @math , and @math . If @math then all @math -regular bipartite graphs of order @math have a FTCM, and for @math , it is not the case. We characterize the values of @math , @math , @math , and @math that admit an @math -regular bipartite graph of order @math , with @math , and give a simple construction that creates such a graph with a FTCM whenever possible. Our techniques are based on Hall's marriage theorem, elementary number theory, linear Diophantine equations, properties of integer functions and congruences, and equations involving them.
  @cite_0: One of the most effective ways of minimizing supply demand mismatch costs, with little increase in operational costs, is to deploy valuable resources in a flexible and timely manner to meet the realized demand. This notion of flexible processes has significantly changed operations in many manufacturing and service companies. For example, a flexible production system is now commonly used by automobile manufacturers, and a workforce cross-training system is now a common practice in many service industries. However, there is a trade-off between the level of flexibility available in the system and the associated complexity and operating costs. The challenge is to have the “right” level of flexibility to capture the bulk of the benefits from a fully flexible system, while controlling the increase in implementation costs. This paper reviews developments in process flexibility over the past decade. In particular, we focus on the phenomenon, often observed in practice, that a slight increase in process flexibility can lead to a significant improvement in system performance. This review explores the issues from three perspectives: design, evaluation, and applications. We also discuss how the concept of process flexibility has been deployed in several manufacturing and service systems.
summary: Design of fault-tolerant bipartite graphs has potential applications in the design of flexible processes, where there are @math different request types and @math servers that should process them (see, for example, the work of @cite_0 for a review of the topic).