Dominator sequences in bipartite graphs

Let G = (V, E) be a bipartite graph with bipartition X, Y and let vertical bar X vertical bar <= vertical bar Y vertical bar. A dominator sequence in G is a sequence of vertices (x(1), x(2), ... , x(k)) in X such that for each i with 2 <= i <= k, vertex x(1) dominates at least one vertex in Y which is not dominated by x(1), x(2), ... , x(i-1). The maximum length of a dominator sequence in G is called the dominator sequence number of G and is denoted by l(G). In this paper we present several basic results on this parameter. We prove that the decision problem for the parameter l(G) is NP-Complete. We obtain bounds for l(G) and discuss applications in the study of optical networks. (C) 2017 Elsevier B.V. All rights reserved.