Connectivity, persistence and fault diagnosis of interconnection networks based on Ok and 2Ok graphs

Various fault-tolerance performance parameters including enumeration of openly disjoint paths, persistence, and resilience of odd graphs Ok and their doubly bipartite derivatives, 2Ok, are analyzed in this paper. Using a remarkable partitioning property of these graphs, the paper proposes an efficient semi-distributed fault-diagnosis scheme for these networks. It is shown through the performance parameters that both Ok and 2Ok graphs have a high degree of fault tolerance and allow efficient fault diagnosis which make these networks comparable or even superior to some other well-known dense networks.