On the L-Grundy domination number of a graph

Abstract

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 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$ is not totally dominated by any vertex that precedes it in the sequence, or, $v$ totally dominates at least one vertex that was 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, ${\gamma_{\rm gr}^{L}}(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 ${\gamma_{\rm gr}^{L}}(G)$ when $G$ is a regular graph, and investigate graphs $G$ on $n$ vertices for which ${\gamma_{\rm gr}^{L}}(G) = n$.