OPTIMAL NODE FAULT TOLERANCE

property

 at least ceil((k + 2)(n + k)/2) edges

 where G is the n-node cycle C,. If G* is an (n + k)-node k-NFT(C,), the degree of every node in G* is at least k + 2

Theorem

 Theorem 1.the Hamiltonian-connected graphs with n + 1 nodes and the smallest number of edges, are optimal 1-NFT( Cn) graphs

  Subtopic 1

 Theorem 2. Let k = 2h when k is even and k = 2h + 1 when k is odd.

  Subtopic 1

 Theorem 3 For every k >=1, the two sets of graphs k-NFT(P_n) = ( k - l)-NFT(C_{n+I})

 Theorem 4.

  Subtopic 1

   Subtopic 1

   K( 1, 1,. . . , 1, n - 1) = K_k + K_( I,n - 1 ),

  Subtopic 2

EXACT FAULT TOLERANCE

 definiiton

 Theorem 5. Graph G* is an exact 1-NFT supergraph of G if and only if G* is node-symmetric

Near-optimal Fault Tolerance