NODE FAULT-TOLERANCE IN GRAPHS

A graph G is a k-node fault-tolerant supergraph of a graph G, denoted k-NFT(G), if every graph obtained by removing k nodes from G contain s G. A k-NFT(G) graph G is said to be optimal if it contains n + k no des, where n is the number of nodes of G and G has the minimum number of edges among all (n + k)-node R-NFT supergraphs of G. We survey pri or results on the design of optimal k-NFT supergraphs of various usefu l forms of G; this work covers cycles and various types of trees. We a lso introduce the concept of exact node fault tolerance, which require s that every graph obtained by removing k nodes from G be isomorphic to G, and explore its basic properties. We conclude with a discussion of some unsolved and partially solved problems. (C) 1996 John Wiley & Sons, Inc.