On the L-grundy domination number of a graph


Boštjan Brešar, Tanja Gologranc, Michael A Henning, Tim Kos




In this paper, we continue the study of the L-Grundy domination number of a graph introduced and first studied in [Grundy dominating sequences and zero forcing sets, Discrete Optim. 26 (2017) 66–77]. A vertex in a graph dominates itself and all vertices adjacent to it, while a vertex totally dominates another vertex if they are adjacent. A sequence of distinct vertices in a graph G is called an L-sequence if every vertex v in the sequence is such that v dominates at least one vertex that is not totally dominated by any vertex that precedes v in the sequence. The maximum length of such a sequence is called the L-Grundy domination number, γ L gr (G), of G. We show that the L-Grundy domination number of every forest G on n vertices equals n, and we provide a linear-time algorithm to find an L-sequence of length n in G. We prove that the decision problem to determine if the L-Grundy domination number of a split graph G is at least k for a given integer k is NP-complete. We establish a lower bound on γ L gr (G) when G is a regular graph, and investigate graphs G on n vertices for which γ L gr (G) = n.