One node fault tolerance for caterpillars and starlike trees

Abstract

For a given tree T with n nodes, we say that a supergraph G tolerates T (having one faulty node) if for each node u of G the subgraph G-u contains T up to isomorphism. Then G tolerates T optimally if G has just one new node and no supergraph of T with n + 1 nodes having fewer edges than G tolerates T. The one-node fault tolerance edge cost of T is the number of new edges in G. We derive theorems which determine this cost exactly for two type of trees, namely, caterpillar and starlike trees.

Keywords:

• Caterpillar
• edge cost
• fault tolerance
• spare node
• starlike tree

^* Research Sponsored in part by Official of Naval Research grant N00014-90-J-I860

^* Research Sponsored in part by Official of Naval Research grant N00014-90-J-I860

Notes

^* Research Sponsored in part by Official of Naval Research grant N00014-90-J-I860