Grundy domination of forests and the strong product conjecture (Q831340)

For any graph \(G\), a sequence of vertices \(S = (v_1,\dots, v_k)\) is called a legal sequence if for every \(i\in [k]\), \(N[v_i]-\cup_{j=1}^{i-1} N[v_j ] \neq\emptyset\). A longest legal sequence is called a Grundy dominating sequence of \(G\) and the size of such a sequence is called the Grundy domination number and is denoted by \(\gamma_{gr}(G)\). The Grundy domination numbers of various graph products are investigated, in particular, it is proved that for any graphs \(G\) and \(H\), \(\gamma_{gr}(G\boxtimes H)\ge \gamma_{gr}(G)\gamma_{gr}(H)\) where \(G\boxtimes H\) is the strong product of graphs \(G\) and \(H\). An outstanding conjecture is that for any graphs \(G\) and \(H\), \[\gamma_{gr}(G\boxtimes H)= \gamma_{gr}(G)\gamma_{gr}(H).\] In this paper, the authors first prove that for any forest \(F\), \(\gamma_{gr}(F) = |V (F)|-|\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. Then using the above result, they show that the aforementioned conjecture is true when \(G\) is a forest. Furthermore, it is proved that every connected graph \(G\) has a spanning tree \(T\) such that \(\gamma_{gr}(G)\le \gamma_{gr}(T)\). Also, it is proved that every non-complete connected graph with at least one edge, contains a Grundy dominating set \(S\) so that the induced subgraph of \(S\) contains no isolated vertices.