کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
5128245 1489490 2017 9 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
Efficient absorbants in generalized de Bruijn digraphs
ترجمه فارسی عنوان
جذب های کارآمد در دیفرانژهای عمومی دیو بریون
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 25, August 2017, Pages 77-85
نویسندگان
, , ,