Grundy dominating sequences on X-join product

GRACIELA NASINI; PABLO TORRES

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2020 vol. 284 p. 138 - 149

0166-218X

In this paper we study the Grundy domination number on the $X$-join product $GR$ of a graph $G$ and a family of graphs $R={G_v: vin V(G)}$. The results led us to extend the few known families of graphs where this parameter can be efficiently computed. We prove that if, for all $vin V(G)$, the Grundy domination number of $G_v$ is given, and $G$ is a power of a cycle, a power of a path, or a split graph, computing the Grundy domination number of $GR$ can be done in polynomial time. In particular, our results for powers of cycles and paths are derived from a polynomial reduction to the Maximum Weight Independent Set problem on these graphs. As a consequence, we derive closed formulas to compute the Grundy domination number of the lexicographic product $Gcirc H$ when $G$ is a power of a cycle, a power of a path or a split graph, generalizing the results on cycles and paths given by Bre sar et al. in 2016. Moreover, our results on the $X$-join product when $G$ is a split graph also provide polynomial-time algorithms to compute the Grundy domination number for $(q,q-4)$ graphs, partner limited graphs and extended $P_4$-laden graphs, graph classes that are high in the hierarchy of few $P_4$´s graphs.