Algorithms for Computing Domination and Total Domination Numbers of RNPCG

Introduction: This paper presents an efficient algorithmic framework for computing the domination number (γ) and total domination number (γt) of graphs, with a focus on applications in collaboration networks. Using a greedy approach combined with minimality verification, the algorithm identifies dominating and total dominating sets that optimize connectivity within the graph structure. Objectives: To design and implement algorithms for computing the domination number of RNPCGs, focusing on both time complexity and practical efficiency. Methods: The methodology is demonstrated on the Rolf Nevanlinna Prize Collaboration Graph (RNPCG), showcasing its ability to handle complex, real-world datasets. Results reveal key insights into the connectivity and influence metrics of prominent academic networks, with implications for optimizing resource dissemination in such systems. The proposed algorithm balances computational efficiency with accuracy, offering a robust tool for graph-theoretic analysis in both theoretical and applied contexts Results: A detailed computational complexity analysis was conducted for both the domination number and total domination number algorithms. It was found that the proposed solutions offer polynomial-time complexity for graphs of moderate size, making them practical for typical use cases. However, the complexity does increase with the size of the graph, especially as the randomness in RNPCGs increases.The algorithms were also compared with exact brute-force solutions for small graphs, showing that our approach provides a significant reduction in computation time while maintaining accuracy. Conclusions: In this study, we developed an efficient algorithm for computing the domination number (γ) and total domination number (γt) in graphs, with a focus on its application to the Rolf Nevanlinna Prize Collaboration Graph (RNPCG). By leveraging a greedy approach and minimality verification, the algorithm effectively identified dominating and total dominating sets, providing insights into the connectivity and structural properties of the RNPCG. The analysis revealed the influence and connectivity of key vertices, illustrating the practical utility of domination metrics in understanding complex collaboration networks. The results emphasize the significance of domination parameters in optimizing resource dissemination and maintaining connectivity within academic or similar real-world networks.