2023/10/16 by Boštjan Brešar, Brešar, Boštjan, Arti Pandey +3 · 2 citations
Computer Science · #Advanced Graph Theory Research #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2310.10566
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.