An Optimization Framework for Balanced Network Coverage Using Mean Absolute Deviation Domination in Graphs

Abstract

Domination in graphs is a fundamental concept in graph theory with important applica-tions in network design and resource allocation. Classical parameters such as the domination number and equitable domination number measure the size and fairness of dominating sets but do not quantify the imbalance in domination coverage. To address this limitation, we introduce a deviation-based measure called the mean absolute deviation of domination, de-noted by MAD(D), which evaluates the uniformity of domination across vertices. Two mixed integer linear programming formulations are proposed to compute minimum-MAD dominat-ing sets and equitable domination numbers. Computational experiments on several graph families demonstrate that graph topology significantly influences domination balance and computational performance.