A maximum sequence $S$ of vertices in a graph $G$, so that every vertex in $S$ has a neighbor which is independent, or is itself independent, from all previous vertices in $S$, is called a Grundy dominating sequence. The Grundy domination number, $\gamma_{ gr}(G)$, is the length of $S$. We show that for any forest $F$, $\gamma_{ gr}(F)=|V(T)|-|\mathcal{ P}|$ where $\mathcal{ P}$ is a minimum partition of the non-isolate vertices of $F$ into caterpillars in which if two caterpillars of $\mathcal{ P}$ have an edge between them in $F$, then such an edge must be incident to a non-leaf vertex in at least one of the caterpillars. We use this result to show the strong product conjecture of B. Bre\v{ s}ar, Cs. Bujt\'{ a}s, T. Gologranc, S. Klav\v{ z}ar, G. Ko\v{ s}mrlj, B. Patk\'{ o}s, Zs. Tuza, and M. Vizer, Dominating sequences in grid-like and toroidal graphs, Electron. J. Combin. 23(4): P4.34 (2016), for all forests. Namely, we show that for any forest $G$ and graph $H$, $\gamma_{ gr}(G \boxtimes H) = \gamma_{ gr}(G) \gamma_{ gr}(H)$. We also show that every connected graph $G$ has a spanning tree $T$ so that $\gamma_{ gr}(G)\le \gamma_{ gr}(T)$ and that every non-complete connected graph contains a Grundy dominating set $S$ so that the induced subgraph of $S$ contains no isolated vertices.
Categories: math.CO