Grundy domination of forests and the strong product conjecture

Kayla Bell ; Keith Driscoll ; Elliot Krop¹ ; Kimber Wolff

¹Clayton State University

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

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šar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B.~Patkó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.

Détail

DOI : 10.37236/9507

Classification : 05C69, 05C76
Mots-clés : Grundy dominating sequence, Grundy domination number, forest, strong product of graphs