DOUBLE DOMINATING SEQUENCES IN BIPARTITE AND CO-BIPARTITE GRAPHS

In a graph G = (V, E), a vertex u E V dominates a vertex v E V if E NG[u]. A sequence S = (v1,v2, ... , vk) of vertices of G is called a double dominating sequence of G if (i) for each i, the vertex vi dominates at least one vertex u E V which is dominated at most once by the previous vertices of S and, (ii) all vertices of G have been dominated at least twice by the vertices of S. GRUNDY DOUBLE DOMINATION problem asks to find double dominating sequence of maximum length for a given graph G. In this paper, we prove that the decision version of the problem is NP-complete for bipartite and co-bipartite graphs. We look for the complexity status of the problem in the class of chain graphs which is a subclass of bipartite graphs. We use dynamic programming approach to solve this problem in chain graphs and propose an algorithm which outputs a Grundy double dominating sequence of a chain graph G in linear-time.