The shortest routing path in star graphs with faulty clusters

Given a graph G, a cluster C is a connected subgraph of G, and C is called a faulty cluster if all nodes in C are faulty. Given an n-dimensional star graph G_n with n-2 faulty clusters of diameter at most 2, it has been shown by the authors (1994) that any two non-faulty nodes s and t of G_n can be connected by a fault-free path of length at most d(G_n)+6 in O(n²) time, where d(G_n)=[(3(n-1))/2] is the diameter of G_n . In this paper, we prove that a fault-free path s→t of length at most d(G_n)+1 if n>10 or n is odd, or d(G_n )+2 otherwise, can be found in O(n²) time. The length of the path s→t is optimal