Mathematics and Computing for Scientific Innovation Vol. 1

A network can be modelled as a graph, where nodes represent stations (or network antennas) and links represent the communication links between them. In graph theory, several structural and stability parameters, including vertex cover, connectivity, tenacity, colouring, integrity, and domination, have been extensively studied. These parameters primarily examine the relationships among vertices and edges through their neighbourhood structures. In the classical domination concept, every vertex in a graph is either a dominating vertex or is adjacent to at least one dominating vertex, thereby ensuring that every vertex is protected. In this article, we consider simple, connected, and undirected graphs and investigate the concept of the medium domination number, which extends the traditional notion of domination by considering the neighbourhoods of every pair of nodes rather than individual nodes. The fundamental idea of medium domination is that every pair of nodes (representing stations or network antennas) should be simultaneously protected. As a result, the number of nodes that can dominate both nodes in each pair must be ascertained. The graph’s medium domination number is defined as the total number of nodes that dominate each pair of nodes plus its average over all vertex pairs. In this work, we establish several new theoretical results concerning the medium domination number and verify existing results using two efficient computational approaches, namely the Adjacency Algorithm and the Neighbourhood Algorithm, proposed in this article. These algorithms provide a systematic framework for computing the medium domination number and facilitate its application to network analysis and related graph-theoretic problems.