An integer programming approach for solving a generalized version of the Grundy domination number

Abstract

A legal dominating sequence of a graph is an ordered dominating set of vertices where each element dominates at least another one not dominated by its predecessors in the sequence. The length of a largest legal dominating sequence is called Grundy domination number. In this work, we introduce a generalized version of the Grundy domination problem. We explicitly calculate the corresponding parameter for paths and web graphs. We propose integer programming formulations for the new problem, find families of valid inequalities and perform extensive computational experiments to compare the formulations as well as to test these inequalities as cuts in a branch-and-cut framework. We also design and evaluate the performance of a heuristic for finding good initial lower and upper bounds and a tabu search that improves the initial lower bound. The test instances include randomly generated graphs, structured graphs, classical benchmark instances and two instances from a real application. Our approach is exact for graphs with 20-50 vertices and provides good solutions for graphs up to 10000 vertices.