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_12: Abstract A d-starlike tree (or a d-quasistar ) is a subdivision of a star tree of degree d . A family of hypercube-like interconnection networks, called restricted hypercube-like graphs , includes most non-bipartite hypercube-like networks found in the literature such as twisted cubes, crossed cubes, Mobius cubes, recursive circulant G ( 2 m , 4 ) of odd m , etc. In this paper, we prove that given an arbitrary fault-free vertex r in an m -dimensional restricted hypercube-like graph with a set F of faults (vertex and or edge faults) and d positive integers, l 1 , l 2 , … , l d , whose sum is equal to the number of fault-free vertices minus one, there exists a d -starlike tree rooted at r , each of whose subtrees forms a fault-free path on l i vertices for i ∈ 1 , 2 , … , d , provided | F | ≤ m − 2 and | F | + d ≤ m . The bounds on | F | and | F | + d are the maximum possible.
  @cite_2: This paper showed the pancyclicity of Cartesian product graphs with faulty edges.This paper showed the bipancyclicity of Cartesian product graphs with faulty edges.Determining the edge-fault pancyclicity (bipancyclicity) of NQ m r , ? , m 1 efficiently.Determining the edge-fault pancyclicity (bipancyclicity) of GQ m r , ? , m 1 efficiently. Let r? 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to 2 ? n ( G ) 2 ? , where n ( G ) is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to n ( G ) , where r ? 3 . A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where n ( G ) , n ( H ) ? 9, let k 1 , k 2 ? 5 be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph G × H with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of NQ m r , ? , m 1 and GQ m r , ? , m 1 .
summary: A related line of research is not to design the smallest fault tolerant graphs (in terms of any metric, like the ones given above), but to analyze the level of fault tolerance assured by prescribed topologies @cite_2 @cite_12 . This topic is of particular interest for algorithm design in high performance computing. Supercomputers are comprised of many processing nodes (with some local memory) that use an interconnection network to communicate during the execution of distributed algorithms. An algorithm delegates computational tasks to different nodes, and uses some logical topology for its message passing. This logical topology has to be somehow embedded in the interconnection network provided by the supercomputer. So it is of practical interest to study if the message passing topologies most common in algorithm design (like cycles, and trees of certain types) can still be embedded in interconnection topologies provided by supercomputers (often similar to hypercubes) when the system presents some faults @cite_2 .