Dominator sequences in bipartite graphs

Let G=(V,E) be a bipartite graph with bipartition X,Y and let |X|≤|Y|. A dominator sequence in G is a sequence of vertices (x1,x2,…,xk) in X such that for each i with 2≤i≤k, vertex xi dominates at least one vertex in Y which is not dominated by x1,x2,…,xi−1. The maximum length of a dominator sequence in G is called the dominator sequence number of G and is denoted by ℓ(G). In this paper we present several basic results on this parameter. We prove that the decision problem for the parameter ℓ(G) is NP-Complete. We obtain bounds for ℓ(G) and discuss applications in the study of optical networks.