Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5128245 | Discrete Optimization | 2017 | 9 Pages |
Let D=(V,A) be a digraph with vertex set V and arc set A. An efficient absorbant (respectively, dominating set) of a digraph D=(V,A) is a set SâV such that, for every vâVâS, there exists exactly one out-neighbor (respectively, in-neighbor) of v in S and there is no arc in the induced digraph of S, where an out-neighbor (respectively, in-neighbor) of v in S is a vertex u with an arc (v,u) (respectively, (u,v)) in A with uâS. The efficient absorbant conjecture is as follows: there is an efficient absorbant in generalized de Bruijn digraph GB(n,d) if and only if nd+1 is a multiple of gcd(n,dâ1), where gcd(x,y) denotes the greatest common divisor of integers x and y. The sufficient condition of this conjecture was proved in DOI:10.1080/00207160.2016.1154949. In this paper, we settle the conjecture. Moreover, we also show that, the subclasses in GB(n,d) having efficient absorbants and efficient dominating sets are equivalent.