Header menu link for other important links
X
Dominator sequences in bipartite graphs
, Arumugam S, Thulasiraman K.
Published in Elsevier BV
2017
Volume: 694
   
Pages: 34 - 41
Abstract
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. © 2017 Elsevier B.V.
About the journal
JournalData powered by TypesetTheoretical Computer Science
PublisherData powered by TypesetElsevier BV
ISSN0304-3975
Open Access0