Grundy Double Domination Number: Bounds, Graph Operations, and Efficient Computation for P4-Tidy Graphs

Abstract

Inspired by graph domination games, various domination-type vertex sequences have been introduced, including the Grundy double dominating sequence (GDDS) of a graph and its associated parameter, the Grundy double domination number (GDDN). The decision version of the problem of computing the GDDN is known to be NPcomplete, even when restricted to split graphs and bipartite graphs. In this paper, we establish general tight bounds for the GDDN. We also describe GDDSs for vertexremoved graphs and for the join of two graphs. Applying these results, we prove that computing the GDDN is linear for P4-tidy graphs, thereby solving an open problem previously posed for cographs by B. Brešar et al. in [Brešar, B., Pandey, A., Sharma, G.: Computational aspects of some vertex sequences of grundy domination-type. Indian J. Discrete Math. 8, 21–38 (2022)].