|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|5128245||1489490||2017||9 صفحه PDF||سفارش دهید||دانلود کنید|
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.
Journal: Discrete Optimization - Volume 25, August 2017, Pages 77-85