Finite Order Domination in Graphs

Abstract

The (previously studied) notions of secure domination and of weak Roman domination involve the construction of protection strategies in a simple graph \( G = (V, E) \), by utilizing the minimum number of guards needed at vertices in \( V \) to protect \( G \) in different scenarios (these minimum numbers are called the secure [weak Roman] domination parameters for the graph). In this paper, these notions are generalized in the sense that safe configurations in \( G \) are not merely sought after one move, but rather after each of \( k \geq 1 \) moves. Some general properties of these generalized domination parameters are established, after which the parameter values are found for certain simple graph structures (such as paths, cycles, multipartite graphs, and products of complete graphs, cycles, and paths).

Keywords: Secure & weak Roman Domination, Higher Order Domination, Graph Protection.