Journal of Innovations in Computer Science and Engineering (JICSE)

Abstract The de Bruijn graph, initially proposed as a topological architecture for interconnection networks, offers unique attributes. These graphs are regular, Eulerian, and Hamiltonian, boasting a small diameter close to optimal connectivity. Their low average distance, small diameter, and high connectivity contribute to remarkable fault tolerance against both node and edge failures. Comprehensively, these graphs serve as pivotal components in word-representing networks, finding applications in various scientific and engineering domains, particularly in genome assembly. They play a significant role in bioinformatics, information theory, coding, communication networks, and multiprocessors. Additionally, de Bruijn graphs are utilized in peer-to-peer (P2P) networks and distributed hash tables (DHT), demonstrating their versatility. Moreover, de Bruijn graphs can serve as a robust infrastructure for modeling online/offline user behavior. In this article, we delve into the different types of de Bruijn graphs and their unique properties from a graph theory perspective. Our focus is on evaluating the reliability of these graphs concerning resilience, fragility, and vulnerability to random failures and targeted attacks on both nodes and edges.

Abstract Moore and Shannon introduced a probabilistic model in which network nodes are assumed to be completely reliable, and communication links or edges can fail with a given probability, such as p. The main problem is determining the probability that the network will remain connected under these conditions, meaning establishing a route between the source and destination terminals. If all links are operational with the same probability of p, the reliability of the entire network is described as a function of p, leading to the reliability polynomial of the network. Moore and Shannon proposed their reliability analysis on specific networks known as hammock networks. Such networks can be well adapted to array-based circuits such as FinFET, VSFET, MOSFET, NEMS, and CNFETs. In this article, focusing on hammock networks, we utilize their combination to design and implement MOS-based transistors, i.e., nMOS and pMOS, and implement basic logical gates based on such networks. To determine the reliability polynomial coefficients, various methods have been presented, most of which exhibit computational complexity due to the recursive property. In practice, for circuits with large orders and sizes, the exact calculation of reliability polynomial coefficients falls into the NP-hard complexity class. In this study, while reviewing the existing problems, efficient methods have been employed to determine the polynomial coefficients of reliability. To ensure fair and accurate comparisons and evaluations, simulation results are utilized to extract performance and reliability measures for all circuits. The reliability of the investigated networks is then compared and analyzed.