Computation of Grundy dominating sequences in (co-)bipartite graphs

Abstract

A sequence $S$ of vertices of a graph $G$ is called a dominating sequence of $G$ if $(i)$ each vertex $v$ of $S$ dominates a vertex of $G$ that was not dominated by any of the vertices preceding vertex $v$ in $S$, and $(ii)$ every vertex of $G$ is dominated by at least one vertex of $S$. The Grundy Domination problem is to find a longest dominating sequence for a given graph $G$. It has been known that the decision version of the Grundy Domination problem is NP-complete even when restricted to chordal graphs. In this paper, we prove that the decision version of the Grundy Domination problem is NP-complete for bipartite graphs and co-bipartite graphs. On the positive side, we present a linear-time algorithm that solves the Grundy Domination problem for chain graphs, which form a subclass of bipartite graphs.

18 pages, 3 figures