Node fault tolerance in graphs

✍ Scribed by Harary, Frank; Hayes, John P.

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 405 KB
• Volume: 27
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199601)27:1<19::aid-net2>3.0.co;2-h

✦ Synopsis

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* contains G. A k-NFT(G) graph G* is said to be optimal if it contains n + k nodes, where n is the number of nodes of G and G * has the minimum number of edges among all ( n + k )node k-NFT supergraphs of G. We survey prior results on the design of optimal k-NFT supergraphs of various useful forms of G; this work covers cycles and various types of trees. We also introduce the concept of exact node fault tolerance, which requires 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. 0 7996 John Wiley & Sons, Inc.