ONE NODE FAULT-TOLERANCE FOR CATERPILLARS AND STARLIKE TREES

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 co ntains 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 edg es 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 t rees.