Grundy domination of forests and the strong product conjecture

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)=\mathrm{\mid }V(T)\mathrm{\mid }-\mathrm{\mid }\mathcal{P}\mathrm{\mid }$ 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)$\mathrm{.}Wealsoshowthateveryconnectedgraph$G$hasaspanningtree$T$sothat$\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.